Question: Given an array of N integer such that only one integer is repeated. Find the repeated integer in O(n) time and constant space. There is no range for the value of integers or the value of N

For example given an array of 6 integers as 23 45 67 87 23 47. The answer is 23
(I hope this covers ambiguous and vague part)

I searched on the net but was unable to find any such question in which range of integers was not fixed.
Also [here](http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html) is an example that answers a similar question to mine but here he created a hash table with the highest integer value in C++.But the cpp does not allow such to create an array with 2^64 element(on a 64-bit computer).

I am sorry I didn't mention it before the array is immutable

Answer: 
If the range of the integers is bounded, you can perform a [counting sort](https://en.wikipedia.org/wiki/Counting_sort) variant in O(*n*) time. The space complexity is O(*k*) where *k* is the upper bound on the integers(\*), but that's a constant, so it's O(1).

If the range of the integers is unbounded, then I don't think there's any way to do this, but I'm not an expert at complexity puzzles.

(\*) It's O(k) since there's also a constant upper bound on the number of occurrences of each integer, namely 2.
We can do in linear time o(n) here as well

```
public class DuplicateInOnePass {

    public static  void duplicate()

   {
        int [] ar={6,7,8,8,7,9,9,10};
        Arrays.sort(ar);
        for (int i =0 ; i <ar.length-1; i++)
        {

            if (ar[i]==ar[i+1])
                System.out.println("Uniqie Elements are" +ar[i]);

        }  

    }

    public static void main(String[] args) {
        duplicate();
    }
}

```