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

Since the number of occurrences of '1' in a binary string of length \(n\) can be \(0, 1, 2, \cdots, n\) (there are \(n + 1\) possibilities), we can certainly find a new binary string that has a different number of '1's from every string in nums.

We can use an integer \(mask\) to record the occurrence of '1' in all strings, i.e., the \(i\)-th bit of \(mask\) is \(1\) indicates that there is a string of length \(n\) in which '1' appears \(i\) times, otherwise it does not exist.

Then we start to enumerate the number of times '1' appears in a binary string of length \(n\) from \(0\). If the \(i\)-th bit of \(mask\) is \(0\), it means that there is no string of length \(n\) in which '1' appears \(i\) times. We can return this string as the answer.

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

Python3JavaC++GoTypeScriptC#

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

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);
            }
        }
    }
}

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');
            }
        }
    }
};

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)
        }
    }
}

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);
        }
    }
}

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

TypeScriptJavaScript

function findDifferentBinaryString(nums: string[]): string {
    const set = new Set(nums.map(x => Number.parseInt(x, 2)));
    let res = 0;

    while (set.has(res)) {
        res++;
    }

    return res.toString(2).padStart(nums[0].length, '0');
}

function findDifferentBinaryString(nums) {
    const set = new Set(nums.map(x => Number.parseInt(x, 2)));
    let res = 0;

    while (set.has(res)) {
        res++;
    }

    return res.toString(2).padStart(nums[0].length, '0');
}

Solution 3

TypeScriptJavaScript

function findDifferentBinaryString(nums: string[]): string {
    const res: string[] = [];

    for (let i = 0; i < nums.length; i++) {
        const x = nums[i][i];
        res.push(x === '0' ? '1' : '0');
    }

    return res.join('');
}

function findDifferentBinaryString(nums) {
    const res = [];

    for (let i = 0; i < nums.length; i++) {
        const x = nums[i][i];
        res.push(x === '0' ? '1' : '0');
    }

    return res.join('');
}

Comments