Find Unique Binary String

Updated on 29 May, 2025
Find Unique Binary String header image

Problem Statement

The task described in the problem is to find a binary string that does not exist within a given array of unique binary strings, where each string has a length equivalent to the size of the array, n. The goal is to construct and return any binary string of length n that is not already present in the array nums. Each string in nums exclusively comprises the characters '0' and '1', making the potential number of binary combinations finite and directly related to n.

Examples

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.

Approach and Intuition

  1. Given that the possible binary strings of length n are 2^n and there are only n strings provided in the array, there exists at least one binary string that does not appear in the list, as long as n < 16.

  2. Begin by understanding the simple cases:

    • When n = 1, the binary strings are just "0" and "1". If one is given, the other is omitted.
    • When n = 2, the possibilities are "00", "01", "10", and "11".
  3. For small values of n, consider manually checking each possibility to see if it's missing from the given list. This brute-force technique becomes infeasible as n increases.

  4. Opt for a systematic approach for higher values of n:

    • Transform each binary string in the list to its decimal equivalent and use a boolean array to mark its presence.
    • Iterate from 0 up to 2^n - 1, and check the first unmarked position in the boolean array. This index, converted back to binary, will provide the missing string.
  5. A direct implementation might involve checking each binary string generated from 0 to 2^n - 1 and ensuring it's not in nums. Convert each integer to binary, ensuring it has n bits (pad with leading zeroes if necessary), and then check if it doesn't exist in nums.

  6. Considering the constraints, ensure that the implementation is efficient for the upper limit where n = 16. This means generating and checking up to 65536 (or 2^16) strings, which is feasible with modern computational power.

Each approach hinges on understanding that it's guaranteed by the problem constraints that at least one valid binary string of length n is absent from nums, simplifying the search process by eliminating the need for exhaustive confirmation that a solution exists.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    string uniqueBinaryString(vector<string>& bits) {
        string result;
        for (int j = 0; j < bits.size(); j++) {
            char bit = bits[j][j];
            result += (bit == '0') ? '1' : '0';
        }
        
        return result;
    }
};

The provided C++ solution addresses the problem of finding a unique binary string from a vector of binary strings. The approach involves creating a new binary string where each bit is determined by flipping the corresponding diagonal bit of the input string at index j. Specifically, if the bit is '0', it is changed to '1', and if it is '1', it is changed to '0'. This guarantees that the resulting binary string will be unique compared to each string in the list, as it differs by at least one bit in the diagonal positions.

The algorithm iterates through each string in the vector, examining and flipping the bit at the index corresponding to the string's position in the list, effectively using a diagonal traversal of the bits matrix. The result is a string that cannot be found in the original list of binary strings, ensuring its uniqueness.

java
class Solution {
    public String generateUniqueBinary(String[] input) {
        StringBuilder result = new StringBuilder();
        for (int index = 0; index < input.length; index++) {
            Character currentChar = input[index].charAt(index);
            result.append(currentChar == '0' ? '1' : '0');
        }
        
        return result.toString();
    }
}

The solution presented generates a unique binary string given an array of binary strings. The Java method generateUniqueBinary in the Solution class is imperative for solving this. Let's break down the working of this code:

  • Initialization: A StringBuilder named result is initiated to help in building the resultant binary string.
  • Iteration through the Input Array: The code loops through each string in the provided array of binary strings.
  • Bit Flipping Logic: For each string, it takes the character located at the position corresponding to the current index of the loop. It flips the bit (from '0' to '1' or from '1' to '0') and appends this flipped bit to the result.
  • Result Compilation: After iterating through all the strings, the accumulated characters in the result StringBuilder form the unique binary string.

This method ensures that the generated binary string will not match any of the binary strings in the given array, leveraging Cantor's diagonal argument by flipping the diagonal bits. The final string is returned as the output of the method.

python
class Solution:
    def findUniqueBinaryStr(self, numbers: List[str]) -> str:
        result_str = []
        for index in range(len(numbers)):
            present_char = numbers[index][index]
            result_str.append("1" if present_char == "0" else "0")
        
        return "".join(result_str)

The Python solution provided constructs a unique binary string from a list of binary strings by ensuring that each character in the resulting string differs from the corresponding character at the same index in each string of the list. Here's an overview of how the solution is implemented:

  • Initiate an empty list called result_str.
  • Iterate through each binary string in the input list using its index.
  • For each position in the binary string, check the character at the current index.
  • Append a '1' to result_str if the character is '0', or a '0' if the character is '1'. This guarantees that the new string will differ from each input string at least at one respective position.
  • After iterating through all binary strings, join the list result_str into a single string.

The resultant string is unique among the input list of binary strings, as it directly counters each character at every index in each string in the list.

Comments

No comments yet.