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.
I_m_rude
Recommended Answers
Jump to PostXor all the numbers as you input them. at the end you will left with the number occurs once.
Jump to PostXor 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?
Jump to Postif 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 = 11 is the ans. works only if all numbers occurs twice and only one number occurs once.
All 10 Replies
Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster
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.
I_m_rude
do u think it is going to rum in 1 sec ?
shanki himanshu
27
Light Poster
Xor all the numbers as you input them. at the end you will left with the number occurs once.
WaltP
commented:
Nice! Didn't know that!
+14
Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster
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_m_rude
commented:
first time, god of C asking a question :D
+2
shanki himanshu
27
Light Poster
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.
Ancient Dragon
commented:
slick :)
+14
WaltP
2,905
Posting Sage w/ dash of thyme
Team Colleague
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.
Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster
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.
WaltP
2,905
Posting Sage w/ dash of thyme
Team Colleague
Oops. Missed that...
I_m_rude
i think shanki himanshu has a great solution.
Ancient Dragon
5,243
Achieved Level 70
Team Colleague
Featured Poster
i think shanki himanshu has a great solution.
Then give him some rep to show your appreciation :)
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.