0592MediumArrayHash TableStringBacktracking

An Unissued Badge Code

Tracked in this browser only

Trains the technique from

LeetCode 1980Find Unique Binary String

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A depot stamps access badges with fixed-width codes. A code of width n is a row of n characters where each character is either 0 or 1.

You are handed nums, the list of codes already stamped. It holds exactly n codes, every one of them of width n, and no two of them are the same.

Return a code of width n, again built only from the characters 0 and 1, that does not appear in nums. Usually more than one code qualifies. When that happens, return the qualifying code that comes earliest in dictionary order.

There are 2^n codes of width n and nums lists only n of them, so a qualifying code always exists.

Examples

Example 1

Input: nums = ["000", "001", "010"]
Output: "011"

`011` has width three, uses only `0` and `1`, and is not one of the three stamped codes. Every width-three code ahead of it in dictionary order, namely `000`, `001` and `010`, is stamped.

Example 2

Input: nums = ["1101", "0000", "1000", "0111"]
Output: "0001"

`0001` is unstamped, while `0000` is stamped, so nothing earlier in dictionary order qualifies.

Example 3

Input: nums = ["11010", "01001", "10111", "00011", "11100"]
Output: "00000"

None of the five stamped codes is `00000`, and no width-five code precedes it in dictionary order.

Constraints

n == nums.length
1 <= n <= 16
nums[i].length == n
Every character of nums[i] is either '0' or '1'.
No code appears twice in nums.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_different_binary_string(nums: list[str]) -> str:

Java

public String findDifferentBinaryString(String[] nums)

The intended approach

Time O(n^2): at most n + 1 candidates, each O(n) to render and hash.Space O(n^2) for the set holding n codes of width n.

Dictionary order on codes of equal width is the same as numeric order on the values they spell out, so the answer is the smallest value in `0 .. 2^n - 1` whose zero-padded `n`-character rendering is absent. Load `nums` into a set, then render the values `0, 1, 2, ...` in turn and return the first rendering the set does not contain. Only `n` codes are stamped, so one of the first `n + 1` values must be free and the loop stops there.

Pythonentry point: find_different_binary_string

def find_different_binary_string(nums):
    # O(n^2) time: at most n + 1 candidates are examined and each costs O(n) to
    # render and hash. O(n^2) space for the lookup set of issued codes.
    n = len(nums)
    issued = set(nums)
    width = "0" + str(n) + "b"
    for value in range(n + 1):
        candidate = format(value, width)
        if candidate not in issued:
            return candidate
    return ""

The obvious version

Walk every value from 0 up to 2^n - 1, spell it out bit by bit into a code of width n, and compare that code against each entry of nums with a plain loop. Return the first code no entry matches.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_different_binary_string(nums):
    n = len(nums)
    total = 1
    for _ in range(n):
        total *= 2
    for value in range(total):
        bits = []
        rest = value
        for _ in range(n):
            bits.append("1" if rest & 1 else "0")
            rest >>= 1
        bits.reverse()
        candidate = "".join(bits)
        clash = False
        for issued in nums:
            if issued == candidate:
                clash = True
                break
        if not clash:
            return candidate
    return ""

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in