PreviousNext
Coding/Arrays and strings

Find the ticket number printed more than once

Write codeEasy15 minAmazon and Google style

Your task

A ticket printer should number its tickets from 1 to n. A bug made it print n + 1 tickets, and exactly one number came out on more than one ticket.

Write find_duplicate(nums) that returns the number that repeats.

Input and output:

  • nums: the n + 1 ticket numbers in print order, where n is from 1 to 100,000. Every value is an integer from 1 to n.
  • Returns the repeated number.

Rules:

  • Exactly one value appears more than once. It may appear 2 or more times, so some numbers from 1 to n can be missing.
  • Every other value appears at most once.

Then, in a sentence or two: how would you find it without changing nums and with only a fixed amount of extra memory?

Examples

find_duplicate(nums: list[int]) -> int
Example 1
Inputfind_duplicate([1, 3, 4, 2, 2])
Output2
Example 2
Inputfind_duplicate([2, 5, 9, 6, 9, 3, 8, 9, 7, 1])
Output9