Find Unique Binary String

medium backtracking cantor diagonal

Problem

You are given an array nums of n distinct binary strings, each exactly n characters long. Return any binary string of length n that does not appear in nums. Since there are 2ⁿ possible strings and only n of them are taken, a missing string always exists; if several are missing, any one is accepted.

Inputnums = ["0110","1010","0010","1101"]

Output"1100"

Flipping each diagonal bit (0→1, 0→1, 1→0, 1→0) builds "1100", which differs from nums[i] at position i for every i — so it cannot be in the list.

binary strings (comma-separated, n strings of length n)

def find_different_binary_string(nums):
    n = len(nums)
    ans = []
    for i in range(n):
        bit = nums[i][i]                        # diagonal bit
        ans.append('1' if bit == '0' else '0')  # flip it
    return ''.join(ans)

function findDifferentBinaryString(nums) {
  const n = nums.length;
  let ans = "";
  for (let i = 0; i < n; i++) {
    const bit = nums[i][i];          // diagonal bit
    ans += bit === "0" ? "1" : "0";  // flip it
  }
  return ans;
}

String findDifferentBinaryString(String[] nums) {
    int n = nums.length;
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; i++) {
        char bit = nums[i].charAt(i);       // diagonal bit
        ans.append(bit == '0' ? '1' : '0'); // flip it
    }
    return ans.toString();
}

string findDifferentBinaryString(vector<string>& nums) {
    int n = nums.size();
    string ans;
    for (int i = 0; i < n; i++) {
        char bit = nums[i][i];           // diagonal bit
        ans += (bit == '0') ? '1' : '0'; // flip it
    }
    return ans;
}

Explanation

The obvious route is backtracking: put the n given strings in a hash set, then DFS over binary strings of length n bit by bit and return the first one the set does not contain. Because only n strings are occupied out of 2ⁿ, you are guaranteed to find a miss among the first n + 1 candidates you try, so even that brute force is fast.

But there is a one-pass construction that needs no search at all: Cantor's diagonal argument, the same trick used to prove the real numbers are uncountable. Stack the n strings into an n × n grid of bits and walk down the main diagonal. Build the answer by taking the opposite of each diagonal bit: ans[i] = flip(nums[i][i]).

Why must this answer be missing? Compare ans with any string nums[i]: at position i they disagree by construction, because we deliberately flipped that exact bit. Differing in even one position means the strings are not equal, so ans differs from every row of the grid — a guaranteed miss without ever checking membership.

Walk the default example ["0110","1010","0010","1101"]. The diagonal reads 0, 0, 1, 1 (bit 0 of row 0, bit 1 of row 1, and so on). Flipping each gives 1, 1, 0, 0, so the answer is "1100". It differs from row 0 at bit 0, row 1 at bit 1, row 2 at bit 2, and row 3 at bit 3 — none of the four rows can equal it.

The crucial precondition is that the count of strings equals their length: n rows give us exactly n diagonal positions, one per row, which is just enough to dodge every row once. The construction reads one character per string and appends one character to the answer, so it runs in O(n) time with O(n) space for the output — beating the set-based search, which already pays O(n²) just to hash the inputs.

Time: O(n) Space: O(n)