Welcome to Subscribe On Youtube

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

Solution 2: Construction

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)$.

• Java
• C++
• Python
• Go
• C#
• TypeScript
• Javascript
• Java 2
• C++ 2
• Python 2
• Go 2
• TypeScript 2
• Javascript 2
• C# 2

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

• 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');
              }
          }
      }
  };
  
  
  // Solution 2
  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;
      }
  };
  
  

• 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)
  
  
  # Solution 2
  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)
  
  

• 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)
  		}
  	}
  }
  
  
  // Solution 2
  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)
  }
  
  

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

• 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);
          }
      }
  }
  
  
  // Solution 2
  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('');
  }
  
  

• /**
   * @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);
          }
      }
  };
  
  
  // Solution 2
  /**
   * @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('');
  };
  
  

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

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

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

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

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

• /**
   * @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('');
  };
  
  

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

All Problems

All Solutions