Odd Appearances
November 14, 2017
Today’s exercise is the kind of interview question that I don’t like. If you know the trick, you look like a genius, and if you don’t know the trick, you don’t get the job:
In an unsorted array of integers, find the one integer that appears an odd number of times. You may use O(n) time and O(1) space. For instance, in the array [4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3], the number 2 appears 2 times, the number 3 appears 4 times, the number 4 appears 3 times, and the number 6 appears 2 times, so the correct answer is 4.
Your task is to write a program to find the integer that appears an odd number of times. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
This is great for a perl one liner – probably as compact as I can get!!
perl -e '(delete$X{$_})||($X{$_}=1)for@ARGV;print keys%X,"\n"' 4 3 6 2 6 4 2 3 4 3 3Here’s a solution in Python.
import operator def odd_appearances(l): return reduce(operator.xor, l) l = [4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3] print odd_appearances(l)Output:
I aspire to learn J. It doesn’t prioritize bitwise operations,
but you can access them with the
b.adverb, so the function in question isFor example,
Here’s a solution in x86 assembly.
Here’s a C program that calls the function.
/* main.c */ #include <stdio.h> int odd_appearances(int* array, int n); int main(void) { int array[] = {4,3,6,2,6,4,2,3,4,3,3}; int n = sizeof(array) / sizeof(int); int val = odd_appearances(array, n); printf("%d\n", val); return 0; }Here’s example usage and output.
Lines 10 and 22 of my odd_appearances.s implementation above should both have %ebx, not %ebp. Those lines were intended to save and restore the non-volatile register %ebx, but I mistakenly wrote %ebp. The function works as-is, but doesn’t follow the calling conventions.
You wrote:
The same [bitwise] XOR approach works for other types if you operate on their binary representation (e.g. using Python’s struct module for conversion)…
C++ Code:
#include
using namespace std;
int main(){
int a[20]={0},i,j,n,temp,temp1,c[20]={0};
cout<<“No in array:”;
cin>>n;
cout<<“Array:”;
for(i=0;i<n;i++){
cin>>a[i];
}
return 0;
}
Here’s an implementation in C that works on arbitrary types, based on @DavidScherba’s earlier comment.
Given an array, and the size of the underlying elements, it performs bitwise XOR on the underlying elements, one byte at a time.
I think this same approach could also work for structs, but would require that they’re either packed or padded consistently.
The example below uses floats.
#include <stdio.h> #include <string.h> void odd_appearances(void* array, size_t n_elements, size_t bytes_per_element, void* result) { memset(result, 0, bytes_per_element); for (size_t i = 0; i < n_elements; ++i) { for (size_t j = 0; j < bytes_per_element; ++j) { ((char*)result)[j] ^= ((char*)array)[i*bytes_per_element+j]; } } } int main(void) { float array[] = {9.79, 0.50, 4.3, 3.42, 0.07, 0.07, 0.50, 3.42, 9.79}; size_t n_elements = sizeof(array) / sizeof(float); float result; odd_appearances(array, n_elements, sizeof(float), &result); printf("%f\n", result); }Example build, usage, and output:
Output: