Find the Duplicate Number
MediumThe problem
A list has n + 1 numbers, and every number is between 1 and n. Exactly one value appears more than once (it may appear more than twice). Return that value. Do not change the list.
- Example 1Input: nums = [1, 3, 4, 2, 2]Output: 2
2 is the only number that appears twice.
- Example 2Input: nums = [3, 1, 3, 4, 2]Output: 3
3 appears twice.
- Example 3Input: nums = [2, 2, 2, 2, 2]Output: 2
The repeated value can appear many times.
- 1 ≤ n ≤ 100,000 (so the list has n + 1 numbers)
- Every number is between 1 and n
- Exactly one value is repeated
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Treat each value as a pointer to the index with that number. A duplicate means two arrows into one cell — a cycle.
The idea
Floyd's cycle detection: find where slow and fast meet, restart one pointer from the start, move both one step at a time; they meet at the duplicate.
Target: O(n) time, O(1) space
Go function shape
func findDuplicate(nums []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// FindDuplicate: n+1 numbers in 1..n. Treat each value as a pointer to the index with that number; two
// indexes pointing at the same place means a cycle, and the cycle's entrance is the duplicate (Floyd).
func FindDuplicate(nums []int) int {
slow, fast := nums[0], nums[nums[0]]
for slow != fast {
slow = nums[slow]
fast = nums[nums[fast]]
}
slow = 0 // distance to the cycle entrance is equal from the start and from the meeting point
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return slow
}