Pattern 2: 1. Easy: Find the Duplicate Number

Description: Find the duplicate number in an array containing n + 1 integers where each integer is between 1 and n.

Java

public int findDuplicate(int[] nums)
{ int slow = nums[0], fast = nums[0];
do {

slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); fast = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }

C++

int findDuplicate(vector<int>& nums)
{ int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
fast = nums[0];
while (slow != fast)
{ slow =
nums[slow]; fast =
nums[fast];
}
return slow;
}

Python

def findDuplicate(nums):
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:

break fast = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow