Wednesday, May 20, 2009

The one missing number

This question sounds rather intimidating but when you analyze it deep enough, you will be amazed about the way this problem is solved - "Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element." Many of us might have quickly jumped into the solution in which many fancy data structures are being used. But actually there is a much easier way to solve this problem. The suggested code is as follow. I think the complexity of this suggested algorithm is O(n). It is a linear operation as you can see in the implementation.

public static int missingNumber(int input[]){
int arrSize = input.length;
int totalLength = arrSize + 1;
int missingNumber = 0;
for (int count=1; count <= totalLength; count++) {
missingNumber = missingNumber + count;
if ((count-1) < arrSize) {
missingNumber = missingNumber - input[(count-1)];
}
}
return missingNumber;
}

0 comments:

Post a Comment