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.

## 0 Comments