Skip to content

1980. Find Unique Binary String

Description

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

 

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 16
  • nums[i].length == n
  • nums[i] is either '0' or '1'.
  • All the strings of nums are unique.

Solutions

Solution 1: Counting + Enumeration

Thinking

There are \(n\) strings of length \(n\) but \(2^n\) possible ones. Among \(n+1\) possible Hamming weights only \(n\) appear, so one weight is missing.

A bit mask records seen counts of ones; we return that many ones padded with zeros.

Since the number of '1's in a binary string of length \(n\) can be \(0, 1, 2, \cdots, n\) (a total of \(n + 1\) possibilities), we can always find a new binary string whose count of '1's differs from every string in \(\textit{nums}\).

We use an integer \(\textit{mask}\) to record the counts of '1's across all strings, where the \(i\)-th bit of \(\textit{mask}\) being \(1\) indicates that a binary string of length \(n\) with exactly \(i\) occurrences of '1' exists in \(\textit{nums}\), and \(0\) otherwise.

We then enumerate \(i\) starting from \(0\), representing the count of '1's in a binary string of length \(n\). If the \(i\)-th bit of \(\textit{mask}\) is \(0\), it means no binary string of length \(n\) with exactly \(i\) occurrences of '1' exists, and we can return that string as the answer.

The time complexity is \(O(L)\), where \(L\) is the total length of all strings in \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        mask = 0
        for x in nums:
            mask |= 1 << x.count("1")
        for i in count(0):
            if mask >> i & 1 ^ 1:
                return "1" * i + "0" * (len(nums) - i)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int mask = 0;
        for (var x : nums) {
            int cnt = 0;
            for (int i = 0; i < x.length(); ++i) {
                if (x.charAt(i) == '1') {
                    ++cnt;
                }
            }
            mask |= 1 << cnt;
        }
        for (int i = 0;; ++i) {
            if ((mask >> i & 1) == 0) {
                return "1".repeat(i) + "0".repeat(nums.length - i);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int mask = 0;
        for (auto& x : nums) {
            int cnt = count(x.begin(), x.end(), '1');
            mask |= 1 << cnt;
        }
        for (int i = 0;; ++i) {
            if (mask >> i & 1 ^ 1) {
                return string(i, '1') + string(nums.size() - i, '0');
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func findDifferentBinaryString(nums []string) string {
    mask := 0
    for _, x := range nums {
        mask |= 1 << strings.Count(x, "1")
    }
    for i := 0; ; i++ {
        if mask>>i&1 == 0 {
            return strings.Repeat("1", i) + strings.Repeat("0", len(nums)-i)
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function findDifferentBinaryString(nums: string[]): string {
    let mask = 0;
    for (let x of nums) {
        const cnt = x.split('').filter(c => c === '1').length;
        mask |= 1 << cnt;
    }
    for (let i = 0; ; ++i) {
        if (((mask >> i) & 1) === 0) {
            return '1'.repeat(i) + '0'.repeat(nums.length - i);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {string[]} nums
 * @return {string}
 */
var findDifferentBinaryString = function (nums) {
    let mask = 0;
    for (let x of nums) {
        const cnt = x.split('').filter(c => c === '1').length;
        mask |= 1 << cnt;
    }
    for (let i = 0; ; ++i) {
        if (((mask >> i) & 1) === 0) {
            return '1'.repeat(i) + '0'.repeat(nums.length - i);
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public string FindDifferentBinaryString(string[] nums) {
        int mask = 0;
        foreach (var x in nums) {
            int cnt = x.Count(c => c == '1');
            mask |= 1 << cnt;
        }
        int i = 0;
        while ((mask >> i & 1) == 1) {
            i++;
        }
        return string.Format("{0}{1}", new string('1', i), new string('0', nums.Length - i));
    }
}

Solution 2: Construction

Thinking

Counting bits walks every character. Cantor diagonalization flips \(\textit{nums}[i][i]\) so the result differs from each input in at least one position.

We can construct a binary string \(\textit{ans}\) of length \(n\), where the \(i\)-th bit of \(\textit{ans}\) differs from the \(i\)-th bit of \(\textit{nums}[i]\). Since all strings in \(\textit{nums}\) are distinct, \(\textit{ans}\) will not appear in \(\textit{nums}\).

The time complexity is \(O(n)\), where \(n\) is the length of the strings in \(\textit{nums}\). Ignoring the space used by the answer string, the space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        ans = [None] * len(nums)
        for i, s in enumerate(nums):
            ans[i] = "1" if s[i] == "0" else "0"
        return "".join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int n = nums.length;
        char[] ans = new char[n];
        for (int i = 0; i < n; i++) {
            ans[i] = nums[i].charAt(i) == '0' ? '1' : '0';
        }
        return new String(ans);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        string ans(n, '0');
        for (int i = 0; i < n; i++) {
            ans[i] = nums[i][i] == '0' ? '1' : '0';
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func findDifferentBinaryString(nums []string) string {
    ans := make([]byte, len(nums))
    for i, s := range nums {
        if s[i] == '0' {
            ans[i] = '1'
        } else {
            ans[i] = '0'
        }
    }
    return string(ans)
}

1
2
3
4
5
6
7
8
function findDifferentBinaryString(nums: string[]): string {
    const n = nums.length;
    const ans: string[] = new Array(n);
    for (let i = 0; i < n; i++) {
        ans[i] = nums[i][i] === '0' ? '1' : '0';
    }
    return ans.join('');
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @param {string[]} nums
 * @return {string}
 */
var findDifferentBinaryString = function (nums) {
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; i++) {
        ans[i] = nums[i][i] === '0' ? '1' : '0';
    }
    return ans.join('');
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public class Solution {
    public string FindDifferentBinaryString(string[] nums) {
        int n = nums.Length;
        char[] ans = new char[n];
        for (int i = 0; i < n; i++) {
            ans[i] = nums[i][i] == '0' ? '1' : '0';
        }
        return new string(ans);
    }
}

Comments