287. Find the Duplicate Number

Problem

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 1

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
  var left = 0;
  var right = nums.length - 1;
  while (left < right) {
      var mid = left + Math.floor((right - left) / 2);
      var num = getNum(nums, mid);
      if (num <= mid) {
          left = mid + 1;
      } else {
          right = mid;
      }
  }
  return left;
};

var getNum = function(nums, n) {
    var num = 0;
    for (var i = 0; i < nums.length; i++) {
        if (nums[i] <= n) num++;
    }
    return num;
};

Explain:

nope.

Complexity:

• Time complexity : O(n * log(n)).
• Space complexity : O(1).