Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Test Cases
Input:
(int[]) nums = [1,3,4,2,2]
Output:
(int) 2
Input:
(int[]) nums = [3,1,3,4,2]
Output:
(int) 3
Solution
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[0];
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
slow = nums[0];
while(slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
};package find_the_duplicate_number
func findDuplicate(nums []int) int {
slow := nums[0]
fast := nums[0]
for true {
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast {
break
}
}
slow = nums[0]
for slow != fast {
slow = nums[slow]
fast = nums[fast]
}
return fast
}class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while(slow != fast);
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
}class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow, fast = nums[0], nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return fast