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
Subscribe to:
Post Comments (Atom)
2 comments:
I hope this does the job
Reply Deleteint 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.
How about easy solution using Bit Array
Reply Delete