1980. Find Unique Binary String
Problem Description
The task is to find a binary string of length n
that is not included in the given array nums
, which contains n
unique binary strings of the same length. The binary string to be found should consist only of '0's and '1's and should not match any of the binary strings in the given list. We are also given the freedom to provide any valid string that satisfies the condition in case multiple correct answers exist.
Flowchart Walkthrough
Let's analyze the problem "leetcode 1980. Find Unique Binary String" using the Flowchart to determine if the Backtracking pattern is suitable for solving this problem. Here’s a step-by-step walkthrough:
Is it a graph?
- No: This problem does not utilize graph concepts such as nodes and edges.
Need to solve for kth smallest/largest?
- No: The task is to find a unique binary string among given strings, not to find an element based on its order.
Involves Linked Lists?
- No: The problem is related to strings and does not involve data structures like linked lists.
Does the problem have small constraints?
- Yes: The constraints of the problem are small as it is limited to binary strings of a given size from a set of binary strings. The potential combinations or permutations involved make backtracking a feasible approach.
Brute force / Backtracking?
- Yes: Since the problem deals with constructing strings under constraints to check uniqueness, backtracking is a very effective approach for generating potential solutions and testing their validity against the given set of binary strings.
Conclusion: The flowchart leads to using the Backtracking pattern based on the nature of the problem, which involves finding a unique solution (unique binary string) by possibly exploring multiple configurations (different binary strings not listed in the given set). Thus, backtracking is suitable for iteratively generating and testing binary strings to find a unique one.
Intuition
The intuition behind this solution involves bit manipulation. Since there are n
unique binary strings, and each is n
bits long, there's a possibility that all binary representations from 0 to n-1
are present. However, the pigeonhole principle states that since there are n+1
possible binary numbers from 0 to n
, there must be at least one number not represented by the n
binary strings.
The solution uses a mask
variable to store which of the binary numbers represented by the count of '1's in each string are already present in the given nums
list. A loop goes through the strings and sets a bit in the mask
to 1 for each count of '1's that occurs.
After that, we loop over the possible counts of '1's from 0 to n
and look for a bit in the mask
that is still 0 (which means this count of '1's has not been used). When we find such a bit, we construct a binary string with this count of '1's followed by the necessary count of '0's to make the length n
and return it. This string is guaranteed not to be in the list because we generated it based on a count of '1's not present in the original list.
For example, if n
is 3, and nums
has ["000", "011", "101"], the counts of '1's are 0, 2, and 2 respectively. So, mask
would have bits 0 and 2 set to 1 (00101 in binary). The number of '1's that is not represented is 1 and 3, and thus, the strings "010" or "111" would be valid outputs.
Learn more about Backtracking patterns.
Solution Approach
The code uses the concept of a bit mask and bit manipulation to keep track of the counts of '1's that are present in the given binary strings nums
. The algorithm proceeds as follows:
-
Initialize a variable
mask
to 0. This mask will have its bits set to 1 at positions that correspond to the counts of '1's found in the binary strings fromnums
. -
For each binary string
x
innums
, convert the count of '1's into a position in themask
and set that position to 1. This is done by the operationmask |= 1 << x.count("1")
. In essence, for a stringx
, if it contains 'k' number of '1's, the k-th bit ofmask
is set to 1. -
Obtain
n
, which is the length of the input listnums
(also the length of every binary string innums
). -
Iterate from
i = 0
ton
(inclusive) and check if the bit at the i-th position ofmask
is not set (which means that no string innums
has exactlyi
number of '1's). This is performed by checking ifmask >> i & 1 ^ 1
isTrue
, wheremask >> i
shifts themask
i
times to the right, creating a new mask that has the i-th bit of the originalmask
at the 0-th position. To check if the bit is not set, we use the XOR operation with 1 (& 1 ^ 1
) which will yieldTrue
if and only if the bit was 0. -
When an unset bit is found (
mask >> i & 1 ^ 1
isTrue
), construct the binary string result by concatenatingi
number of '1's withn-i
number of '0's to make the string's length equal ton
. This resultant string is guaranteed to be unique and not to appear innums
. -
Return the constructed string.
For example, if n
is 3, and nums
contains the strings ["000", "011", "101"], the mask
after step 2 would be 5
(in decimal) or 101
in binary as the 0-th and 2-nd bits are set to 1. Looking for an unset bit in mask
, we find that the 1-st and 3-rd positions are 0. Therefore, we can construct the strings "010" or "111" as our output, both of which have a length of 3 and do not appear in nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example with n = 2
and nums
being ["00", "01"]
. We want to find a binary string of length 2 that is neither "00" nor "01".
-
Initialize
mask
to 0. This will be used to track the count of '1's present in the binary strings fromnums
. -
Iterate through each string in
nums
:- For "00", there are 0 '1's. We set the 0-th bit of
mask
usingmask |= 1 << 0
. Nowmask
is01
in binary (1 in decimal). - For "01", there is 1 '1'. We set the 1-st bit of
mask
usingmask |= 1 << 1
. Nowmask
changes from01
to11
in binary (3 in decimal), since both 0-th and 1-st bits are set.
- For "00", there are 0 '1's. We set the 0-th bit of
-
Now that
n
is 2, we check for bits inmask
which are not set. -
We start iterating from
i = 0
ton
(until 2, inclusive):- For
i = 0
: Checkmask >> i & 1 ^ 1
. We havemask >> 0
which is11
(3) and& 1
which gives the last bit '1', then^ 1
would give 0 (False). The 0-th bit is set, so we continue. - For
i = 1
: Checkmask >> i & 1 ^ 1
. We havemask >> 1
which is1
(1) and& 1
which gives '1', then^ 1
would give 0 (False). The 1-st bit is also set, so we continue. - For
i = 2
: Checkmask >> i & 1 ^ 1
. We havemask >> 2
which is0
(0) and& 1
which gives '0', then^ 1
would give 1 (True). The 2-nd bit is not set; this means no string innums
has 2 '1's.
- For
-
As soon as we find an i-th bit not set, we construct the binary string with
i
number of '1's followed byn-i
number of '0's. Sincen=2
andi=2
, we get "11" as the result. This string has exactly 2 '1's, and its length matchesn
. -
Thus, the string "11" is returned. This string is of length
n
, not present innums
, and follows the correct format.
Solution Implementation
1class Solution:
2 def findDifferentBinaryString(self, nums: List[str]) -> str:
3 # Initialize a bitmask to keep track of the count of "1"s in the binary strings
4 bitmask = 0
5
6 # Iterate over each binary string in the nums list
7 for binary_string in nums:
8 # Count the number of "1"s and set the corresponding bit in the bitmask
9 # The bit position is the count of "1"s
10 bitmask |= 1 << binary_string.count("1")
11
12 # Get the length of binary strings in the nums list (assuming they all have the same length)
13 n = len(nums)
14
15 # Find the smallest binary string with a different count of "1"s than those in nums
16 for i in range(n + 1):
17 # Check if there is no binary string in nums with i "1"s
18 if bitmask >> i & 1 ^ 1:
19 # Return the binary string with i "1"s followed by (n - i) "0"s
20 # Ensuring it has the same length as other strings in nums
21 return "1" * i + "0" * (n - i)
22
1class Solution {
2 public String findDifferentBinaryString(String[] nums) {
3 // Initialize a mask to keep track of the counts of 1s found in the binary strings.
4 int mask = 0;
5
6 // Iterate over each binary string in the input array.
7 for (String binaryString : nums) {
8 // Initialize a count for the number of '1's in the current string.
9 int countOnes = 0;
10
11 // Iterate through each character in the binary string.
12 for (int i = 0; i < binaryString.length(); i++) {
13 // If the character is '1', increment the counter.
14 if (binaryString.charAt(i) == '1') {
15 countOnes++;
16 }
17 }
18
19 // Set the corresponding bit in the mask for the count of '1's found.
20 // This will help us to keep track of which counts are already present.
21 mask |= 1 << countOnes;
22 }
23
24 // Start generating different binary strings to find one not in the input.
25 for (int i = 0; ; i++) { // Infinite loop, will break when found a non-existing binary string.
26 // Check if the bit representing the count of '1's at index 'i' is not set.
27 if ((mask >> i & 1) == 0) {
28 // Create a binary string with 'i' number of '1's followed by enough '0's to make it the same length as input strings.
29 // Then return the newly created binary string.
30 String ones = "1".repeat(i);
31 String zeros = "0".repeat(nums.length - i);
32 return ones + zeros;
33 }
34 }
35 }
36}
37
1#include <string>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 std::string findDifferentBinaryString(std::vector<std::string>& nums) {
8 // Initialize a variable to serve as a bitmask where each bit represents
9 // the count of '1's in the binary strings seen so far.
10 int bitmask = 0;
11
12 // Loop through the binary strings.
13 for (auto& str : nums) {
14 // Count the number of '1's in the current string.
15 int countOnes = std::count(str.begin(), str.end(), '1');
16 // Set the corresponding bit in the bitmask.
17 bitmask |= 1 << countOnes;
18 }
19
20 // Loop indefinitely to find a binary string with a different count of '1's.
21 for (int i = 0;; ++i) {
22 // Check if the current count of '1's is not represented in the bitmask.
23 // The expression (bitmask >> i) shifts the bitmask to the right by 'i' bits,
24 // and then checks if the least significant bit is not set.
25 if (((bitmask >> i) & 1) == 0) {
26 // If not set, we found our number. Return a binary string with 'i' ones
27 // followed by enough zeros to match the size of the input binary strings.
28 return std::string(i, '1') + std::string(nums.size() - i, '0');
29 }
30 }
31 // No return is needed here as the loop is guaranteed to return a string
32 // because there are 2^N possible binary strings of length N, and only N of them
33 // have unique counts of '1's, leaving at least one string that is different.
34 }
35};
36
1function findDifferentBinaryString(nums: string[]): string {
2 // Initialize a variable to act as a bitmask where each bit position represents
3 // the count of '1's in the binary strings seen so far.
4 let bitmask: number = 0;
5
6 // Loop through the binary strings.
7 for (let str of nums) {
8 // Count the number of '1's in the current string.
9 let countOnes: number = [...str].filter(c => c === '1').length;
10 // Set the corresponding bit in the bitmask.
11 bitmask |= 1 << countOnes;
12 }
13
14 // Start an infinite loop to find a binary string with a different count of '1's.
15 for (let i = 0; ; ++i) {
16 // Check if the current count of '1's is not yet represented in the bitmask.
17 // The expression (bitmask >> i) shifts the bitmask to the right by 'i' bits,
18 // and then checks if the least significant bit is not set.
19 if (((bitmask >> i) & 1) === 0) {
20 // If not set, we have found our number. Return a binary string with 'i' '1's
21 // followed by enough '0's to match the size of the input binary strings.
22 return '1'.repeat(i) + '0'.repeat(nums[0].length - i);
23 }
24 }
25 // No explicit return is necessary here as the loop condition assures a return,
26 // because there are 2^N possible binary strings of length N, and only N of them
27 // can have unique counts of '1's, ensuring at least one string that is different.
28}
29
30// The method names are not modified and the above function can be used directly.
31// Usage example:
32// let result = findDifferentBinaryString(["01", "10"]);
33// console.log(result); // Outputs a binary string that is different from the input strings
34
Time and Space Complexity
Time Complexity
The time complexity of the given code is determined by iterating over the input list nums
once, and then iterating through a range that is at most n + 1
, where n
is the length of nums
.
-
The first
for
loop iterates over each string innums
and involves a bitwise OR operation as well as counting the number of '1's in each string. Both of these operations occur in constant time (since the strings are of lengthn
and binary string length is fixed in this scenario). Hence, this part of the loop runs inO(n)
time. -
The second
for
loop runs from 0 ton
, and each iteration involves a constant-time operation: a bitwise right shift followed by a bitwise AND, and a bitwise XOR. Therefore, the loop runs inO(n)
time.
Combining both parts, the overall time complexity is O(n + n)
which simplifies to O(n)
.
Space Complexity
The space complexity is determined by the additional space used by the algorithm beyond the input itself.
-
The variable
mask
is an integer that requiresO(1)
space. -
No other additional data structures that grow with the size of the input are used in the algorithm.
Hence, the overall space complexity of the code is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.