The Repeated Ticket

MediumArrays & Hashing

Problem

A raffle drum holds n + 1 tickets, each printed with a number from 1 to n. A printing fault means exactly one number appears more than once (possibly many times); every other number appears at most once.

Return the repeated number without modifying tickets and using only O(1) extra space.

Example 1

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

Example 2

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

Constraints

  • 1 ≤ n ≤ 10^5
  • tickets.length = n + 1
  • 1 ≤ tickets[i] ≤ n
  • Exactly one value is repeated.

Hint

Show the first hint

Treat each value as a pointer: from index i you can jump to index tickets[i]. What structure does that create?

Walkthrough

How to approach it

01Clarify before coding

  • May I sort or mark the array? No, it must stay unmodified.
  • Can the repeated value appear more than twice? Yes, so 'sum minus expected sum' does not work.
  • Is a hash set allowed? No, the space bound is O(1).

02Brute force

For each value, count its occurrences with an inner loop; or sort a copy and look for equal neighbours.

Cost: Double loop: O(n²) time. Sorting a copy: O(n log n) time but O(n) space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.