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