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.

Advertisements

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

  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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: