## Odd Appearances

### November 14, 2017

The obvious answer is to collect the frequency counts in a hash table, then find the item with the odd count, but that violates the O(1) space limit of the problem. The trick is to traverse the array, taking the XOR of each element of the array with the XOR of all the preceding elements of the array. A number that appears an even number of times will be XORed with itself each time it appears, resulting in zero, and the result of the XOR will be the sole number that appears an odd number of times:

`(define (odd-appearances xs) (fold-left bitwise-xor 0 xs))`
```> (odd-appearances '(4 3 6 2 6 4 2 3 4 3 3))
4```

Obviously, this only works for integers. You can run the program at https://ideone.com/5EjX67.

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
```