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.

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: