Find Unique Binary String - Practice Coding Problems

Find Unique Binary String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = ["01","10"]

› Output: "00"

💡 Note: Using diagonal approach: flip bits at positions [0,1] from strings ["01","10"] → flip '0' to '1' and '1' to '0' → "10". Or we can return "00" or "11" as they're not in the input.

Example 2 — Single Element

$ Input: nums = ["0"]

› Output: "1"

💡 Note: Only one string "0" exists, so we return the other possible string "1".

Example 3 — Three Strings

$ Input: nums = ["111","011","001"]

› Output: "101"

💡 Note: Using diagonal: flip bits at positions [0,1,2] from ["111","011","001"] → flip '1','1','1' → "000". Any missing string like "101" is valid.

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

n binary strings of length n

Find Missing

One string must be missing from all 2^n possibilities

Return Any Valid

Any missing string is a correct answer

Key Takeaway

🎯 Key Insight: With n unique strings of length n, exactly 2^n - n strings are missing. We can use Cantor's diagonal argument to construct one efficiently.

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is using Cantor's diagonal argument: construct a string that differs from each input string at position i by flipping the i-th bit of the i-th string. Best approach is diagonal flipping with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Cantor's Diagonal Argument	O(n)	O(n)	Construct answer by flipping diagonal bits to guarantee uniqueness
Generate All Possible Strings	O(n × 2^n)	O(n)	Generate all 2^n possible binary strings and return first one not in input
Backtracking Construction	O(n²)	O(n)	Build string bit by bit, backtrack when current path matches existing string

Cantor's Diagonal Argument — Algorithm Steps

For each position i from 0 to n-1
Look at character at position i in the i-th string
Flip that bit (0→1, 1→0) in our result

Visualization

Tap to expand

Step-by-Step Walkthrough

Diagonal Pattern

Look at i-th bit of i-th string

Flip Each Bit

0→1, 1→0 for diagonal positions

Guaranteed Unique

Result differs from each input string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char** nums, int n) {
    char* result = (char*)malloc((n + 1) * sizeof(char));
    result[n] = '\0';
    
    // Cantor's diagonal argument
    for (int i = 0; i < n; i++) {
        // Flip the i-th bit of the i-th string
        if (nums[i][i] == '0') {
            result[i] = '1';
        } else {
            result[i] = '0';
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for array of strings
    char** nums = (char**)malloc(20 * sizeof(char*));
    int n = 0;
    
    char* token = strtok(line, "[,]\"");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[n] = (char*)malloc(21 * sizeof(char));
            strcpy(nums[n], token);
            n++;
        }
        token = strtok(NULL, "[,]\"");
    }
    
    char* result = solution(nums, n);
    printf("%s\n", result);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(nums[i]);
    }
    free(nums);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through n strings, each operation is O(1)

✓ Linear Growth

Space Complexity

O(n)

Result string of length n

⚡ Linearithmic Space

32.1K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Cantor's Diagonal Argument — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler