# Find the non repeating number in the integer array

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 havent used hashmaps and i know the complexity can reduce to O(n) if I use hashmaps. Can you help me with that?

#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;
}
}
}
}

-

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.

-
@paul : Thanks much.I had to change this part of insert and it worked. hashMap.insert(std::pair<int,int>(number,1)); I like the way how hashmaps take care of indexing and stuff automatically, instead of having the programmer worry abt that. I am not very good at working with indexing (:-). –  user2781 Mar 24 '11 at 20:38

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.

-
how about for(auto i : a) if you have range based for loops, or if not: for(auto i = std::begin(a); i != std::end(a); ++i) –  Dave Mar 11 '13 at 16:38
Why are you using unsigned? It's implied to be unsigned int right? Most correct would be size_t since that's the maximum occurrence count you could conceivably have without going out of memory. –  Dave Mar 11 '13 at 16:40
@Dave I’m using unsigned because negative counts simply don’t make sense. I only use std::size_t when explicitly referring to sizes or offsets of container classes, not when counting natural entities. It wouldn’t be wrong here to use either, per se. –  Konrad Rudolph Mar 11 '13 at 16:51
I meant why are you using unsigned instead of unsigned int? In this case it represents the count in an array, which does fit the bill for what size_t is for. It's the type of the count of an array. If you used std::array instead of int[] you could use std::array::size_type but that's guaranteed to be size_t... just like real arrays. –  Dave Mar 11 '13 at 17:18
@Dave When I wrote this answer I was working on a project where the convention was to use unsigned instead of unsigned int. Since either is valid it doesn’t really matter. I now use unsigned int again in my own code. –  Konrad Rudolph Mar 11 '13 at 19:12

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/

-
This only works if elements are repeating only twice. In other cases it fails (Coz It is XOR operator). The link is Also broken now. –  Vedant Terkar Jan 19 at 4:58

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.

-
Even if you call your variable hashMap, std::map is a treemap and not a hashmap, making your code O(n log n). The current C++ standard does not include a hashmap, but C++0x does under the name unordered_map. So if your compiler is recent enough, you can use std::unordered_map. Otherwise you can use boost. –  sepp2k Mar 24 '11 at 19:58
I didn't know that about std::map, thanks for the clarification. –  Paulo Pinto Mar 24 '11 at 21:42
Now that you do know, it would be a good idea to correct the information in your answer. –  sepp2k Mar 25 '11 at 15:59