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 by I_m_rude

4
Contributors
10
Replies
13
Views
6 Years
Discussion Span
Last Post by Ancient Dragon
Featured Replies
• 1

>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?

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 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.

Nice! Didn't know that!

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?

first time, god of C asking a question :D

if we have an array 3,1,3,2,2
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.

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 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 by Ancient Dragon

Oops. Missed that...

i think shanki himanshu has a great solution.

i think shanki himanshu has a great solution.

Then give him some rep to show your appreciation :)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.