Published May 30, 2022
[
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.
Input: nums = [1,3,4,2,2]
Output: 2
Input: nums = [3,1,3,4,2]
Output: 3
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums appear only once except for precisely one integer which appears two or more times.nums?function findDuplicate(nums: number[]): number {
let slow: number = 0, fast: number = 0;
// find intersection of slow & fast
while(true){
slow = nums[slow]
fast = nums[nums[fast]]
if (slow === fast){
break;
}
}
// find the start of cycle
let slow2: number = 0;
while(true){
slow = nums[slow]
slow2 = nums[slow2]
if(slow === slow2) {
return slow;
}
}
};