1980-find Unique String (Day-08)

Interview Trick: Find a Binary String Not Present in the Array One interesting interview problem asks: Problem You are given n unique binary strings of length n . Return any binary string of length n that does not appear in the array . Example: Input: nums = ["01","10"] Output: "11" // or "00" Brute Force Idea Since each string has length n , there are: 2^n possible binary strings. If we generate all 2^n strings and check which one is missing from the array, we can solve the problem. However, this approach is inefficient. Time Complexity O(2^n * n) Optimal Interview Trick (Diagonal Method) A much smarter approach uses a concept similar to Cantor’s Diagonalization . Idea: Construct a new string by flipping the diagonal bit of each string. ans[i] = flip(nums[i][i]) Where: 0 → 1 1 → 0 Why This Works For every index i : ans[i] ≠ nums[i][i] That means the constructed string differs from the i-th string at position i . Therefore: ans ≠ nums[0] ans ≠ nums[1] ... ans ≠ nums[n-1] So the new str