Find Unique Binary String
MedPrompt
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.length1 <= n <= 16nums[i].length == nnums[i]is either'0'or'1'.- All the strings of
numsare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating all possible binary strings of length n one by one and checking if they exist in the input array nums. To make the checking process efficient, we first convert the input array nums into a HashSet. The first generated string that is not found in the HashSet is our answer.
Algorithm
- Create a
HashSet<String>and add all elements from the input arraynumsto it. This allows for efficient O(1) average time lookups. - Iterate with an integer counter, let's say
i, starting from 0 up to2^n - 1. - In each iteration, convert the integer
ito its binary string representation. - Pad the generated binary string with leading zeros to ensure its length is
n. - Check if this newly formed
n-bit binary string is present in theHashSet. - If the string is not in the set, it means we have found a unique binary string. Return this string.
- Since there are
nstrings innumsout of2^ntotal possibilities, a unique string is guaranteed to be found.
Walkthrough
The total number of distinct binary strings of length n is 2^n. We can represent each of these strings by an integer from 0 to 2^n - 1. The algorithm proceeds as follows:
First, we insert all strings from nums into a HashSet. This data structure provides average O(1) time complexity for checking the existence of an element. Building this set takes O(n^2) time as we have n strings of length n.
Next, we iterate from i = 0 upwards. In each step, we convert the integer i into its n-bit binary string representation. For instance, if n=4 and i=5, the binary is 101, which we pad to 0101. We then check if this generated string is present in our HashSet.
If the string is not in the set, we have found a unique string and can return it immediately. The problem guarantees that nums contains n unique strings, and since 2^n > n for n >= 1, there's always at least one missing string. We are sure to find an answer, at worst, after checking n+1 possibilities.
import java.util.HashSet;import java.util.Set; class Solution { public String findDifferentBinaryString(String[] nums) { Set<String> numSet = new HashSet<>(); for (String s : nums) { numSet.add(s); } int n = nums.length; for (int i = 0; i < (1 << n); i++) { String binary = Integer.toBinaryString(i); // Format to n-bit string with leading zeros String formattedBinary = String.format("%" + n + "s", binary).replace(' ', '0'); if (!numSet.contains(formattedBinary)) { return formattedBinary; } } return ""; // Should not be reached given the problem constraints }}Complexity
Time
O(n^2). Creating the `HashSet` takes `O(n * n)` time. The subsequent loop runs at most `n+1` times, and inside the loop, string generation and hash set lookup each take `O(n)` time. Thus, the total time complexity is dominated by `O(n^2)`.
Space
O(n^2). The `HashSet` stores `n` strings, each of length `n`, leading to a space requirement proportional to the total number of characters.
Trade-offs
Pros
Straightforward and easy to understand.
It is guaranteed to find a solution.
Cons
Inefficient in terms of both time and space compared to the optimal solution.
Requires significant extra space to store the HashSet, which can be large for greater values of
n.
Solutions
Solution
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)); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.