Given an array of **n** elements that contains numbers from **1 to n-1**, with any of these numbers appearing **any number of times in any order (non-sorted)**.

Find these repeating numbers in **O(n) time** and using only **constant memory** space, O(1).

Input: {1, 2, 3, 2, 1, 3, 4}

Output: 2 1 3

## Solutions

### Method 1: Marking elements (-)ve

The idea is to iterate the array from 0 to n-1 and mark the **arr[i]th** element as -ve, if arr[i]th element is -ve print arr[i].

The below code **doesn't work if "0" is present** in the array.

It will not work if the array contains more than 2 duplicates of an element. For example: {1, 2, 3, 1, 1, 3, 4} it will give output as : 1 1 3.

This **more than 2 duplicates issue can be resolved** by iterating the array twice. In the first iteration, mark the element **-ve** only if it is positive, and in the second iteration, print the index of -ve elements.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.

### Method 2: Adding "n" and using modulus "n"

This solution **works for "0" as an element** and also **handles scenarios when there are more than two duplicates of an element** present in the array.

The idea is to iterate the array from **0 to n-1 **and add **"n"** to the element at the **arr[i]th** index.

If any element **"e"** occurs more than once, the **"eth"** index will have a value greater than or equal to **2 * n**.

Iterate the array a second time and print the **"index"** of elements having a value greater than or equal to **2 * n**.

In this solution, only one thing is left to be taken care of. As we are adding **n** to array elements, this will cause an "ArrayIndexOutOfBoundsException" while trying to get "arr[arr[i]]" because arr[i] is also acting as an index and the value will be out of the n-1 range. (n is added to the element at arr[i] for every occurance of "i").

To overcome this, the only change needed is to get **"arr[i] % n"** instead of "arr[i]" - so for an array of length n = 4, if element "3" is present twice and 2 is present at index 3, the element at index 3 will be converted to 2+4=6 and 2+4+4=10.

Now using **"%"**, we can get 6%4 = 2 and 10%4 = 2 (no "ArrayIndexOutOfBoundsException").

##### Complexity

**O(n)**and space complexity is

**O(1)**.