Find the Duplicate Number
Description
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.
Example 1:
Input: nums = [1,3,4,2,2] Output: 2
Example 2:
Input: nums = [3,1,3,4,2] Output: 3
Constraints:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
- All the integers in
nums
appear only once except for precisely one integer which appears two or more times.
Follow up:
- How can we prove that at least one duplicate number must exist in
nums
? - Can you solve the problem in linear runtime complexity?
Solution(javascript)
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function(nums) {
//Traverse the array from start to end.
//For every element,take its absolute value:
//if the abs(array[i])‘th element is positive, the element has not encountered before,
//else if its negative meaning the element has been encountered before, print the absolute value of the current element.
//Works only when there is only one repeated number and nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
//Each encountered element modifies the value in the corresponding index in array and when we reach an element that already was modified -it means that the index already appeared - meaning the element is duplicated.
for (var i = 0; i < nums.length; i++) {
var absNum = Math.abs(nums[i]);
// If not seen yet
if (nums[absNum] >= 0) {
nums[absNum] *= -1;
} else {
return absNum;
}
}
};