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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

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 from nums.
For each binary string x in nums, convert the count of '1's into a position in the mask and set that position to 1. This is done by the operation mask |= 1 << x.count("1"). In essence, for a string x, if it contains 'k' number of '1's, the k-th bit of mask is set to 1.
Obtain n, which is the length of the input list nums (also the length of every binary string in nums).
Iterate from i = 0 to n (inclusive) and check if the bit at the i-th position of mask is not set (which means that no string in nums has exactly i number of '1's). This is performed by checking if mask >> i & 1 ^ 1 is True, where mask >> i shifts the mask i times to the right, creating a new mask that has the i-th bit of the original mask at the 0-th position. To check if the bit is not set, we use the XOR operation with 1 (& 1 ^ 1) which will yield True if and only if the bit was 0.
When an unset bit is found (mask >> i & 1 ^ 1 is True), construct the binary string result by concatenating i number of '1's with n-i number of '0's to make the string's length equal to n. This resultant string is guaranteed to be unique and not to appear in nums.
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example 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 from nums.
Iterate through each string in nums:
- For "00", there are 0 '1's. We set the 0-th bit of mask using mask |= 1 << 0. Now mask is 01 in binary (1 in decimal).
- For "01", there is 1 '1'. We set the 1-st bit of mask using mask |= 1 << 1. Now mask changes from 01 to 11 in binary (3 in decimal), since both 0-th and 1-st bits are set.
Now that n is 2, we check for bits in mask which are not set.
We start iterating from i = 0 to n (until 2, inclusive):
- For i = 0: Check mask >> i & 1 ^ 1. We have mask >> 0 which is 11 (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: Check mask >> i & 1 ^ 1. We have mask >> 1 which is 1 (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: Check mask >> i & 1 ^ 1. We have mask >> 2 which is 0 (0) and & 1 which gives '0', then ^ 1 would give 1 (True). The 2-nd bit is not set; this means no string in nums has 2 '1's.
As soon as we find an i-th bit not set, we construct the binary string with i number of '1's followed by n-i number of '0's. Since n=2 and i=2, we get "11" as the result. This string has exactly 2 '1's, and its length matches n.
Thus, the string "11" is returned. This string is of length n, not present in nums, 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

Not Sure What to Study? Take the 2-min Quiz：

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know

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 in nums 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 length n and binary string length is fixed in this scenario). Hence, this part of the loop runs in O(n) time.
The second for loop runs from 0 to n, 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 in O(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 requires O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1980. Find Unique Binary String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings