# Find the Duplicate Number (Leetcode: 287)

Mar 17th, 2020
143
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate
2. # number must exist. Assume that there is only one duplicate number, find the duplicate one.
3.
4. # You must not modify the array (assume the array is read only).
5. # You must use only constant, O(1) extra space.
6. # Your runtime complexity should be less than O(n2).
7. # There is only one duplicate number in the array, but it could be repeated more than once.
8.
9. class Solution:
10.     def findDuplicate(self, nums: List[int]) -> int:
11.         sp = nums[nums[0]]
12.         fp = nums[nums[nums[0]]]
13.
14.         while sp != fp:
15.             sp = nums[sp]
16.             fp = nums[nums[fp]]
17.
18.         fp = nums[0]
19.
20.         while sp != fp:
21.             sp = nums[sp]
22.             fp = nums[fp]
23.
24.         return fp
RAW Paste Data