Find The Duplicate Number

Medium · Linked List

You are given an array of n+1 integers where every value lies between 1 and n inclusive. Exactly one value is duplicated one or more times while every other value appears exactly once, and you must return that repeated value. You cannot modify the array (treat it as read only) and you should use only constant extra space beyond the input.

Examples

Input:  nums = [1,3,4,2,2]
Output: 2
Why:    The value 2 appears twice while the rest of the numbers from 1 to 4 appear once, so 2 is the repeated value.

Input:  nums = [3,1,3,4,2]
Output: 3
Why:    The value 3 appears twice while the rest of the numbers from 1 to 4 appear once, so 3 is the repeated value.

Input:  nums = [1,1]
Output: 1
Why:    With only the value 1 possible besides the length, it must be the one that repeats.

Constraints

1 <= nums.length <= 10^5, each value in nums is between 1 and nums.length - 1 inclusive, and exactly one value repeats (it may repeat more than once) while the array is otherwise a permutation of 1..n-1

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Find The Duplicate Number

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Find The Duplicate Number. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.