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

Pages: 1 2

### 9 Responses to “Odd Appearances”

1. 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 3
```
2. Daniel said

Here’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:

```4
```
3. 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 is

```25 b./
```
4. For example,

```   25 b./4 3 6 2 6 4 2 3 4 3 3
4
```
5. Daniel said

Here’s a solution in x86 assembly.

```/* odd_appearances.s */

.section .text

# int odd_appearances(int* array, int n);
.globl odd_appearances
odd_appearances:
pushl %ebp
movl  %esp, %ebp
pushl %ebp
movl  8(%ebp), %ebx  # array
movl  12(%ebp), %ecx # n
movl  \$0, %eax
movl  \$0, %edx       # index
loop:
cmpl  %ecx, %edx
jae   done
xorl  (%ebx, %edx, 4), %eax
incl  %edx
jmp   loop
done:
popl  %ebp
movl  %ebp, %esp
popl  %ebp
ret
```

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.

```\$ as --32 -o odd_appearances.o odd_appearances.s
\$ gcc -m32 -o main odd_appearances.o main.c
\$ ./main
```
```4
```
6. Daniel said

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.

7. David Scherba said

You wrote:

Obviously, this only works for integers.

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)…

8. C++ Code:

#include
using namespace std;

int main(){
int a={0},i,j,n,temp,temp1,c={0};
cout<<“No in array:”;
cin>>n;
cout<<“Array:”;
for(i=0;i<n;i++){
cin>>a[i];
}

``````for(i=0;i<n;i++){
c[i]=1;
for(j=i+1 ; j<n ; j++){
if ( a[i]==a[j] ) {
c[i] += 1;

}
}
}

for(i=0;i<n;i++){
//c[i]=1;
for(j=i+1 ; j<n ; j++){
if ( c[i]<c[j] ) {
temp=c[i];
c[i]=c[j];
c[j]=temp;
temp1=a[i];
a[i]=a[j];
a[j]=temp1;

}
}
}

for(i=0;i<n;i++){
if(a[i]%2 != 0){
cout<<"The no. is: "<<a[i];
break;
}
}
``````

return 0;
}

9. Daniel said

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:

```\$ c99 -Wall -o odd_appearances odd_appearances.c
\$ ./odd_appearances
```

Output:

```4.300000
```