#287

Find the Duplicate Number

specialist · 670 · lc medium +30 · verified · 64% accepted · 25,380 likes · top 67%

⚑ Fast & Slow Pointers (Floyd's Cycle)⚑ Cyclic Sort

Description

An array nums holds n + 1 integers where every value is in the range [1, n]. Exactly one number appears more than once. Find and return that repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]

Output: 2

Example 2:

Input: nums = [3,1,3,4,2]

Output: 3

Example 3:

Input: nums = [3,3,3,3,3]

Output: 3

Code

1

2

3

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:

class Solution:
    def findDuplicate(self, nums: List[int]) -> int: