Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
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
I hope this does the job
ReplyDeleteint 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
ReplyDelete