we are getting i/p of 5,00,000 numbers ranging from 0 to 10^9 one by one. all numbers appears twice except one. We have to tell that number in the most efficient way. Any idea or just a hint to get this ? no code, no algo nothing i want. i want just a simple hint from you. thanks.

Edited 4 Years Ago by I_m_rude

I_m_rude
Deleted Member

I don't know if this is the "most efficient" way, but one way to do it is to have an array of integers, then fill the array with numbers as they are read from the file. When you find a number that appears a second time delete it from the array. When done check the array for undeleted numbers. To delete a number just make it -1 since that is not a valid number is your data file.

Another possibility is to create a linked-list of the numbers, add a node when a number is read from the file that is not in the list, and delete the node when the number is read from the file that is already in the list. When done, the linked list should contain only one node. This will probably run a lot slower the the previous suggestion.

Edited 4 Years Ago by Ancient Dragon

do u think it is going to rum in 1 sec ?

Xor all the numbers as you input them. at the end you will left with the number occurs once.

Can you elaborate on that? A couple examples please?

Comments
first time, god of C asking a question :D

if we have an array 3,1,3,2,2
then do xor all the numbers start with 0.
0^3 = 3
3^1 = 2
2^3 = 1
1^2 = 3
3^2 = 1

1 is the ans. works only if all numbers occurs twice and only one number occurs once.

Comments
slick :)

4th option:
Make a zeroed array of 5,00,000 integers.
For every integer read, use it as an index into the array and increment that entry. When done, the value that's 1 was read once.

But shanki himanshu's solution seems to be the most efficient. It's a really slick solution.

Edited 4 Years Ago by WaltP

Sorry Walt, but that won't work. The range of numbers is 0 to 10^9, which requires an array 10,000,000,000 elements.

Edited 4 Years Ago by Ancient Dragon

i think shanki himanshu has a great solution.

This article has been dead for over six months. Start a new discussion instead.