Find the non repeating number in the integer array
If the array is sorted you do not need hashmaps to achieve O(n). If you have a random/unsorted array you can use hashmaps to achieve the purpose, see Paulo's answer for that. Note that sorting requires O(n log(n)).

If you want to know how often each integer is in the original collection you will also need hashmaps, but if you only want to know a nonduplicate number in a sorted array the following code will work:

// N is the number of ints in sorted
int nonduplicate(int sorted[], const int N){
    //To prevent segfaulting when N=1
    if(N==1){ return sorted[0]; };

    for(int i=0;i &lt; N-1;i++){
        if(sorted[i] == sorted[i+1]){
            // Next number in collection is the same so the current number is not unique
            // Set i to the first location of the next different number
            do{
                i++;
            }while(i &lt; N-1 &amp;&amp; sorted[i] == sorted[i+1]);
        }else{
            // The next number is different so the current is unique
            return sorted[i];
        }
    }
    // Is the last number unique?
    if(sorted[N-1] != sorted[N-2]){
        return sorted[N-1];
    }
    // No unique numbers
    return -1;    // Or some other value you reserve for it
}


Note that this code is faster because it doesn't have the overhead of a hashmap and may stop before traversing the whole array, but does have the same big-O limit.