## 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.

This is great for a perl one liner – probably as compact as I can get!!

Here’s a solution in Python.

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.

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.

Example build, usage, and output:

Output: