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;
        }
    }   
};