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.