0094MediumArrayTwo PointersBinary SearchBit ManipulationPigeonhole PrincipleFloyd's Cycle Finding Algorithm

Duplicate Bin Code

Tracked in this browser only

Trains the technique from

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 packing line drops every parcel into one of n numbered chutes, labelled 1 through n. The shift log codes records the chute label used for each parcel, and the shift handled n + 1 parcels, so codes has length n + 1.

One chute was wired to two buttons, so its label got reused: exactly one label occurs two or more times in codes, and every other label that occurs at all occurs exactly once. Some labels may never occur.

Return the label that was reused.

The log is archived material: your routine must leave codes unchanged and use only a constant amount of extra space beyond the input.

Examples

Example 1

Input: codes = [4, 2, 4, 1, 3]
Output: 4

Five parcels were logged, so there are four chutes. Label 4 shows up at positions 0 and 2 while labels 1, 2 and 3 each show up once.

Example 2

Input: codes = [6, 3, 6, 6, 2, 5, 1]
Output: 6

Seven parcels means six chutes. Label 6 was used three times, labels 1, 2, 3 and 5 once each, and label 4 never came up.

Example 3

Input: codes = [1, 1]
Output: 1

With a single chute and two parcels, that one label has to carry both.

Constraints

1 <= n <= 10^5
codes.length == n + 1
1 <= codes[i] <= n
Exactly one label occurs two or more times; every other label present occurs exactly once
codes must not be modified, and only O(1) extra space may be used

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 reused_chute(codes: list[int]) -> int:

Java

public int reusedChute(int[] codes)

The intended approach

Time O(n)Space O(1)

Read the log as a jump table: from position `i`, hop to position `codes[i]`. Every label lies in `1..n`, so position 0 is never a landing spot, which means the walk that starts at 0 enters a loop it cannot be part of. The only position with two incoming hops is the reused label, so it is exactly where the loop begins. Run a slow and a fast walker until they land together, then restart one walker at 0 and advance both one hop at a time; they reunite at the loop entrance.

Pythonentry point: reused_chute

def reused_chute(codes):
    slow = 0
    fast = 0
    while True:
        slow = codes[slow]
        fast = codes[codes[fast]]
        if slow == fast:
            break
    walker = 0
    while walker != slow:
        walker = codes[walker]
        slow = codes[slow]
    return walker

The obvious version

Compare every pair of log entries directly and return the first label found twice, O(n^2).

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_reused_chute(codes):
    total = len(codes)
    for i in range(total):
        for j in range(i + 1, total):
            if codes[i] == codes[j]:
                return codes[i]
    return -1

How this problem was checked

Reference solution executed against 9 test cases — 9 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