Practice Projects

Find Unique Binary String

Problem Statement

  • Aapko ek array of strings diya gaya hai, jismein n unique binary strings hain aur har string ki length n hai. Aapko ek aisi binary string return karni hai jiska length n ho aur jo nums mein nahi hoti. Agar multiple answers ho, to aap koi bhi return kar sakte hain.

    Example 1:

    • Input: nums = ["01","10"]

    • Output: "11"

    • Explanation: "11" nums mein nahi hoti. "00" bhi sahi hoga.

    Example 2:

    • Input: nums = ["00","01"]

    • Output: "11"

    • Explanation: "11" nums mein nahi hoti. "10" bhi sahi hoga.

    Example 3:

    • Input: nums = ["111","011","001"]

    • Output: "101"

    • Explanation: "101" nums mein nahi hoti. "000", "010", "100", aur "110" bhi sahi honge.

    Constraints:

    • n == nums.length

    • 1 <= n <= 16

    • nums[i].length == n

    • nums[i] sirf '0' ya '1' hote hain.

    • Saari strings nums mein unique hain.

Practice Projects

Find Unique Binary String

Main idea yeh hai:

Hum ek string "000...0" se shuru karte hain jiska length n hai, aur check karte hain agar yeh nums mein exist karti hai.

Agar yeh string already nums mein hai, toh hum bits ko ek ek karke flip karte hain '1' mein aur phir se check karte hain.

Jab tak humein pehla valid string milta hai, wahi humara answer hoga.Agar saari combinations exist karti hain (jo chhote n ke liye highly unlikely hai), toh worst case mein O(2^n) strings check karni padengi.

Approach

Time Complexity: O(n^2)

  • Matlab worst case mein, humein lagbhag n strings check karni padti hain jinki length n hoti hai.

Space Complexity: O(1)

  • Matlab hum sirf kuch extra variables use karte hain, toh space requirement constant hoti hai aur input size ke sath nahi badhti.

Solution

				
					class Solution {
    findDifferentBinaryString(nums) {
        let ans = '0'.repeat(nums.length);  // "000...0" se shuru karo
        
        if (!nums.includes(ans)) return ans;  // Check karo agar yeh already work karta hai

        for (let i = 0; i < nums.length; i++) { 
            ans = ans.substring(0, i) + '1' + ans.substring(i + 1);  // Ek bit ko flip karo '1' mein
            if (!nums.includes(ans)) 
                return ans;  // Agar yeh valid hai, return kar do
            ans = ans.substring(0, i) + '0' + ans.substring(i + 1);  // Agar valid nahi hai toh wapas '0' kar do
        }
        return ans;  // Fallback case
    }
}

    • The solution begins by creating a binary string of all zeroes with the same length as the input array nums.

    • It then checks if this all-zeroes string is already present in nums. If it is not, this all-zero string is returned as the answer.

    • If the all-zeroes string is found in nums, the solution attempts to find a unique binary string by flipping one bit at a time to ‘1’ and checking if the new string is present in nums.

    • If the new string is not present in nums, it is returned as the answer.

    • If the new string is present, the bit is reverted back to ‘0’, and the process continues with the next bit.

    • The solution continues this process until it finds a valid binary string that is not present in nums or until all bits have been checked.

Solution

				
					class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        string ans = string(nums.size(), '0');  // "000...0" se shuru karo
        
        if(find(nums.begin(), nums.end(), ans) == nums.end()) return ans;  // Check karo agar yeh already work karta hai

        for(int i = 0; i < nums.size(); i++) { 
            ans[i] = '1';  // Ek bit ko flip karo '1' mein
            if(find(nums.begin(), nums.end(), ans) == nums.end()) 
                return ans;  // Agar yeh valid hai, return kar do
            ans[i] = '0';  // Agar valid nahi hai toh wapas '0' kar do
        }
        return ans;  // Fallback case
    }
};