Saturday, February 20, 2010

Find what is missing

You are given an unsorted list of n-1 distinct integers from the range 1 to n. Write a linear-time algorithm to find the missing integer. Please pay attention to potential overflow
Pubblicato da a
Reazioni: 

2 comments:

  1. I hope this does the job

    int missing ( int * arr, int n) {
    int ans= 0, tmp = 0, i =0;
    for (i = 0; i < n ; i++) {
    tmp^=i;
    ans^=arr[i];
    }
    tmp^=i;tmp^=(i+1);
    return tmp^ans;
    }

    Sorry for the unformatted code. I don't know how to post formatted code on blogspot.

    ReplyDelete

  2. How about easy solution using Bit Array

    ReplyDelete

Subscribe to: Post Comments (Atom)