Leetcode 1980. Find Unique Binary String

This is the daily question of leetcode in 2025-02-20. {: .prompt-info }

Problem Description

#

Given array of strings nums containing n unique binary strings of length n, return a binary string of length n that does not appear in nums.

Intuition

#

• This can be done by Cantor’s diagonal argument, so, we just implement it.

Approach

#

1. We observe that nums is an array containing n different binary strings, each of length n.

2. To generate a new string that is guaranteed to be unique:

   • We traverse the diagonal elements of nums (i.e. nums[i][i]).

   • If nums[i][i] is ‘$0$’, we change it to ‘$1$’.

     If nums[i][i] is ‘$1$’, we change it to ‘$0$’.

3. Since our new string differs from nums[i] at the i-th position, it cannot be identical to any of the given binary strings.

Code

#

string findDifferentBinaryString(vector<string>& nums) {
        string result = "";
        for(int i = 0; i < nums.size(); i++){
            result += (nums[i][i] == '0') ? '1' : '0';
        }
        return result;
    }

Time Complexity: $O(n)$

Space Complexity: $O(1)$ as we doesn’t count answer as part of space.

Thank you for reading! Let me know your thoughts and feedback! {: .prompt-tip }