Show problems as
Classic problem #287MediumArrayTwo PointersBinary SearchBit ManipulationPigeonhole PrincipleFloyd's Cycle Finding Algorithm

Find the Duplicate Number

Real-world version: Duplicate Bin Code
Tracked in this browser only
Read Find the Duplicate Number on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def reused_chute(codes: list[int]) -> int:
Java
public int reusedChute(int[] codes)

More on the same topics