Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• C#

• 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();
      }
  }
  
  ############
  
  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);
              }
          }
      }
  }
  

• // OJ: https://leetcode.com/problems/find-unique-binary-string/
  // Time: O(N^2)
  // Space: O(N)
  class Solution {
  public:
      string findDifferentBinaryString(vector<string>& A) {
          int n = A.size();
          unordered_set<int> s;
          for (auto &n : A) {
              s.insert(stoi(n, 0, 2));
          }
          for (int i = 0; i <= n; ++i) {
              if (s.count(i)) continue;
              string ans;
              for (int j = 0; j < n; ++j) {
                  ans += '0' + (i & 1);
                  i >>= 1;
              }
              reverse(begin(ans), end(ans));
              return ans;
          }
          return "";
      }
  };
  

• 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)
  
  ############
  
  # 1980. Find Unique Binary String
  # https://leetcode.com/problems/find-unique-binary-string/
  
  class Solution:
      def findDifferentBinaryString(self, nums: List[str]) -> str:
          n = len(nums)
          s = set(nums)
          
          for i in range(1 << n):
              x = bin(i)[2:].zfill(n)
              if x not in s:
                  return x
  
  

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

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

All Problems

All Solutions