Good problem
An integer array of size 101 contains 51 numbers between 1-10000.
50 nos are stored twice.
how can u find the no which is stored once??
The solution might be very simple. Get an algorithm of the time complexity O(n) and the least utilization of memory.
One Solution is...
Find out the XOR of all the numbers. The result of this is the required answer, which also takes O(n) and one extra memory location for storing the result.
50 nos are stored twice.
how can u find the no which is stored once??
The solution might be very simple. Get an algorithm of the time complexity O(n) and the least utilization of memory.
One Solution is...
Find out the XOR of all the numbers. The result of this is the required answer, which also takes O(n) and one extra memory location for storing the result.
posted by srividya at
9:31 PM
3 Comments:
1. search in google for an answer.
2. Make a hash function of each number to generage unique id. place in hash table of 10000.
Take a hash with unique id as key and value is index/the count. When colision occurs values will two indexes/count 2. The number which is not repeated will have just one entry.
3.
WILL POST SOLUTION IN 1 or 2 DAYS
By
manjunath, at 10:20 AM
But the requirement is to have least utilization of memory. This solution will also work but takes more memory, what i feel.
By
srividya, at 9:35 PM
u have to choose between flags and 10000 hash keys. I think algorithm wise this is o(n).
Memory is always trade off. I'm sure there are better solutions.
By
manjunath, at 7:47 PM
Post a Comment
<< Home