1980. Find Unique Binary String

Time: O(n)

Space: O(n)

Intuition

Find n+1 bit binary strings not in the array. Since there are 2^n possible n-bit strings but only n given, at least one is missing. Iterate and check.

Algorithm

1Build set of existing strings.
2Generate all n-bit strings (0..2^n-1). Return first not in set.

Common Pitfalls

•2^n total possibilities, only n strings given. Iterate 0..2^n and find missing. For large n, use clever generation.

1980.cs

// Approach: Cantor's diagonal — flip the i-th bit of nums[i] to guarantee the result differs from every string.
// Time: O(n) Space: O(n)

public class Solution
{
    public string FindDifferentBinaryString(string[] nums)
    {
        StringBuilder sb = new StringBuilder();

        // Flip the i-th bit for each nums[i] so that `ans` is unique.
        for (int i = 0; i < nums.Length; ++i)
            sb.Append(nums[i][i] == '0' ? '1' : '0');

        return sb.ToString();
    }
}

Was this solution helpful?