CareerCup

You already got the answer, just xor them all, the result is the one showing odd times.

As the question says, only one interger occurs odd number of times.
If you XOR any number with itself, it will result in 0. Thus, you can think of it as all integers which occur even number of times will cancel out each other.

Hence the final number which would remain at last will be the number which had odd-frequency.

int find_duplicate_element( int * elements, int n) {

int dup;
for(int i = 0 ; i < n ; i++){
if(elements[elements[i] - 1] < 0) {
//elements[i] -1 to account for array starting from 0
dup = elements[i];
break;
}
else{
elements[elements[i] - 1] = - elements[elements[i] - 1];
}
}

for(int i = 0 ; i < n ; i ++) {
elements[i] = elements[i] < 0 ? -elements[i] : elements[i] ;
}
return dup;
}

sorry corrected version of above code, didnt note integers are in the range 0 to n-1

int find_duplicate_element( int * elements, int n) {

int dup;
for(int i = 0 ; i < n ; i++){
if(elements[elements[i]] < 0) {

dup = elements[i];
break;
}
else{
elements[elements[i]] = - elements[elements[i]];
}
}

for(int i = 0 ; i < n ; i ++) {
elements[i] = elements[i] < 0 ? -elements[i] : elements[i] ;
}
return dup;
}

How about the solution based on RadixSort?

public int findSingle(int A[]) {
if(A == null || A.length == 0)
return -1;
for(int i=0; i<A.length; i++) {
while(i != A[i]) {
if(A[i] == A[A[i]])
return A[i];
else{
int tmp = A[A[i]];
A[A[i]] = A[i];
A[i] = tmp;
}
}
}
return -1;
}

As already mentioned,XOR each invidividual bits: Java solution my attempt: Optimization can be done not to through all the 32 bits of integer.. Time Complexity :O(32N) Space: O(1)

private static int findOddOccurenceNum(int [] integers) {
		//get the ith bit
		int missingNum = 0;
		for (int i = 0; i < 32; i++) {
			int missingBit = 0;
			for (int j = 0; j < integers.length; j++) {
				missingBit = missingBit ^ (integers[j] & (1<<i) );
			}
			if(missingBit!=0) {
				missingNum |= (1<<i);
			}
		}
		return missingNum;
	}
	
	public static void main(String[] args) {
		int [] integers = new int  [] {-2,2,2,3,3};
		System.out.println(findOddOccurenceNum(integers));
	}

hi,

Is the input always sorted?

If the quetion is as @gocool has restated

"The question is that there is an array of size N and values range from 0 to N-1. Every integer occurs once except one that occurs odd number of times(instead of some of the integers - so atleast two of the numbers in the sequence from 0 to N-1 is missing). We find that number that occur odd number of times( &gt; 1)."


Then
Number = sum of array - sum of from 0 to N-1