The Lost Ticket

Easy

A raffle printed tickets numbered 0 through n, which is n + 1 tickets in total. One of them got lost; the other n are in the array tickets in no particular order, with no number repeated. Return the number of the lost ticket. Try to solve it in O(n) time with O(1) extra memory.

Example 1

tickets=[4, 0, 2, 1] → 3

There are 4 tickets, so the numbers ran from 0 to 4. Only 3 is missing.

Example 2

tickets=[1, 2] → 0

The numbers run from 0 to 2, and 0 is missing.

Example 3

tickets=[0] → 1

The numbers run from 0 to 1; the last one, 1, is missing.

Constraints

n = len(tickets)
1 ≤ n ≤ 10⁵
0 ≤ tickets[i] ≤ n
All numbers in tickets are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Hash Table Math Binary Search Sorting

Similar problems

Values in Both Lists Easy Shared Values With Repeats Easy Doubled Tag, Lost Tag Easy Even Out the Shelves Easy Twice as Much Easy

Input

tickets=[4, 0, 2, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 43 tests on the server, hidden ones included.