Given an array of say 1 Billion entries and its is filled with numbers ranging from 1 to 1 Billion
and there can be duplicates of the same number, given a number(between 1 and 1 Billion), whats
the easiest method to find whether the entry is a duplicate in the array.
Subscribe to:
Post Comments (Atom)
Assuming there is only one duplicate. We can use the fact that m*(m+1)/2 gives the sum of numbers from 0 to n-1. Subtracting this result from actual sum of the numbers in given array. The result will be duplicate number.
ReplyDeletefor(i = 0; i < n-1; i++)
s = s+a[i];
dup = s - (n(n+1))/2;
This is one solution. Obviously, next question comes to our mind, What if there are more than one duplicate? Well, lets find out solution for that too.
No, that does not work.
ReplyDeleteTake for ex: 1 2 3 3 5 , the sum is 14 but sum for consecutive numbers is 15. The difference between these totals is 1 but duplicate is 3.
Solution is to sort the array and then find out the duplicates.
ReplyDelete