Programming Praxis

Odd Appearances

November 14, 2017 10:00 AM

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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

9 Responses to “Odd Appearances”

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
```
By James Curtis-Smith on November 14, 2017 at 10:29 AM

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:

By Daniel on November 14, 2017 at 3:33 PM

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./
```
By Graham Enos on November 15, 2017 at 12:08 AM
For example,
```
   25 b./4 3 6 2 6 4 2 3 4 3 3
4
```
By Graham Enos on November 15, 2017 at 12:10 AM

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

By Daniel on November 15, 2017 at 1:28 AM

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.

By Daniel on November 15, 2017 at 1:34 AM
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)…

By David Scherba on November 15, 2017 at 6:45 PM

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];
}

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;
}

By Aman Tripathi on November 16, 2017 at 7:45 AM

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

By Daniel on November 17, 2017 at 2:25 AM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Odd Appearances

Share this:

Related

9 Responses to “Odd Appearances”

Leave a Reply