Find the non repeating number in the integer array

Question

The program finds the non repeated number in a int array. I am using a count for the duplicates and making a Numcounts[] to store the count values. I am assuming the array is sorted. Then I can check the Numcounts[] for 1, and that would be the non-repeating number. The complexity is \$O(n^2)\$.

Can you tell me how to do the same thing using hashmaps? I haven't used hashmaps and I know the complexity can be reduced to \$O(n))\$ using them.

#include<stdafx.h>
#include<stdio.h>

int main()
{
    int n=6;
    int * Numcounts = new int[n];
    int count = 0;
    int a[6] = {1,1,1,2,2,3}; // sort the array before proceeding.Because in the else part count is set to zero. 
    //If the array is unsorted then count will be reset in middle and will not retain the previous count.
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i]==a[j])
            {
                count = count+1;
                Numcounts[i] = count;
            }
            else{
                count = 0;
            }
        }
    }
}

Answer 1

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 < 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 < N-1 && 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.

Answer 2

Since you are using C++ and not C, there are a few things that you could clean up.

First of all, your code leaks memory: you are newing memory but you are not deleteing. In order to avoid this manual memory management, you should use the std::vector class template instead of new[].

Furthermore, stdio.h is a legacy C header. Use cstdio in C++. But in fact, your code doesn’t need that header anyway.

A hash map implementation is available in the std::tr1 namespace. If your compiler supports this (modern compilers do), the following code works:

#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<int, unsigned> occurrences;
    int a[6] = { 1, 1, 1, 2, 2, 3 };
    unsigned const size = sizeof a / sizeof a[0];

    // First pass: count occurrences.
    for (unsigned i = 0; i < size; ++i)
        ++occurrences[a[i]];

    // Second pass: search singleton.
    for (unsigned i = 0; i < size; ++i)
        if (occurrences[a[i]] == 1)
            std::cout << a[i] << " only occurred once." << std::endl;
}

(To enable TR1 support on GCC, pass the std=c++0x flag to the compiler.)

Point of interest: the first pass works because the values inside the unordered map (= hash map) are initialised with the default value, 0. We are using this fact to increment the values directly without bothering to check whether the value existed in the map beforehand. This makes the code more concise and is actually also more efficient.

Answer 3

A hashmap is a structure that maps a key (the hash) to a value.
In your example you'd want the key to be the number and the value to be the count of each number. If you are using a compiler that that supports C++0x, you can add

#include <unordered_map>

and then modify the body of your main loop to something like:

std::unordered_map<int, int> hashMap;
for(int i=0;i<n;i++)
{
    int number = a[i];

    // check if this number is already in the map
    if(hashMap.find(number) != hashMap.end())
    {
        // it's already in there so increment the count
        hashMap[number] += 1;
    }
    else
    {
        // it's not in there yet so add it and set the count to 1
        hashMap.insert(number, 1);
    }
}

I wrote this code down from memory so it might not even compile, although it should be straightforward to fix.

As you can see we only run through the array once so you now have the O(n) complexity.

Answer 4

Actually, you could do it in \$O(N)\$ using XOR to bitshift things.

This will do it will less overhead and much faster (in java, since that is what I know):

public static void main(String... args) {
    int[] x = new int[] { 5,7,4,9,5,7,4 };
    int result = 0;
    for (int i=0;i<x.length;i++) {
        result ^= x[i];
    }
    System.out.println("result:"+result);
}

Good article on this here: http://kaipakartik.amplify.com/

Answer 5

This can easily be done in \$O(n)\$: run through the array and find the largest value. Create a vector of this size initialized to zeros. Run through the array and increment the element in the vector indexed by each value by one. Finally, run through the vector and find the element equal to one; the offset of this element in the vector is your answer.