leetcode - 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.
1
2
3

Example 2:

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

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.
1
2
3

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.
1
2
3
4
5

Solution

Brute Force

Since n is not big, just go from 0 to $2^n$ to find the missing value. Remember to pad 0 at the left for each binary number.

Time complexity: $o(2^n\ast n)$
Space complexity: $o(1)$

string

Sort the nums, and starts with 0, every time if the number equals to the number in nums, then current number plus 1, until the current number is not the same as the number in nums.

Time complexity: $o(n\log n)$
Space complexity: $o(1)$

Cantor’s diagonal

Solved after help, this is so brilliant!!

Construct a string, the 1st digit is different with 1st number, and the 2nd digit is different with 2nd number, then after go through all the numbers we get the final results. since it’s different with all the numbers.

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

Brute Force

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        for i in range(2**n):
            binary_string = bin(i)[2:]
            binary_string_pad = '0' * (n - len(binary_string)) + binary_string
            if binary_string_pad not in nums:
                return binary_string_pad
1
2
3
4
5
6
7
8

String

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        prev = '0' * n
        nums.sort()

        def add_one(binary_str: str) -> str:
            binary_num = list(binary_str)
            for i in range(len(binary_num) - 1, -1, -1):
                if binary_num[i] == '1':
                    binary_num[i] = '0'
                else:
                    binary_num[i] = '1'
                    break
            return ''.join(binary_num)

        for each_num in nums:
            if prev == each_num:
                prev = add_one(prev)
            else:
                return prev
        return prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Cantor’s diagonal

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        n = len(nums)
        res = ['0'] * n
        for i in range(n):
            res[i] = '1' if nums[i][i] == '0' else '0'
        return ''.join(res)
1
2
3
4
5
6
7