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 using 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



Sort the given input array. Traverse the array and if the value of the ith element is not equal to i+1, then the current element is repetitive as the value of elements is between 1 and N-1 and every element appears only once except one element.


Follow the below steps to solve the problem:

  • Sort the given array.
  • Traverse the array and compare the array elements with its index 
  • if arr[i] != i+1, it means that arr[i] is repetitive, So Just return arr[i]. 
  • Otherwise, the array does not contain duplicates from 1 to n-1, In this case, return -1  

Algorithm,

const findRepeating = arr => {
    //Sorting Array
    arr.sort(function(a,b){return a-b});

    for (let i = 0; i < arr.length; i++) {
          
    // compare the array element with its index
        if (arr[i] == arr[i + 1]) {
              return arr[i];
            }
        }
        return -1;
}

console.log(findRepeating([ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]));
//8


Time complexity: O(N * log N) 
Auxiliary Space: O(1)

I hope you understood the algorithm, if you have any doubts let us know in the comments.