Formatted question description: https://leetcode.ca/all/1980.html

1980. Find Unique Binary String

Level

Medium

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'.

Solution

The number range of numbers with binary string of length n is [0, 2^n - 1]. Convert all elements in nums into integers, and loop over the integers from 0 to 2^n - 1 and find the first integer that is not in nums.

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int length = nums.length;
        int maxNum = (1 << length) - 1;
        Set<Integer> set = new HashSet<Integer>();
        for (String num : nums)
            set.add(Integer.parseInt(num, 2));
        int different = 0;
        for (int i = 0; i <= maxNum; i++) {
            if (!set.contains(i)) {
                different = i;
                break;
            }
        }
        String differentStr = toBinaryString(different, length);
        return differentStr;
    }

    public String toBinaryString(int num, int length) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            int remainder = num % 2;
            sb.append(remainder);
            num /= 2;
        }
        sb.reverse();
        return sb.toString();
    }
}

All Problems

All Solutions