Member Avatar for Member #957352

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 Member #957352
  • 4 Contributors
  • 10 Replies
  • 120 Views
  • 22 Hours Discussion Span
  • Latest Post Latest Post by Ancient Dragon

Dani AI

Generated

For the input described by (500,000 integers in the range 0..10^9, every value appears exactly twice except one), the simplest and fastest approach is the bitwise XOR trick mentioned by . It is a single pass, uses constant extra memory and runs in linear time — ideal for streaming input.

Why it works: XOR is associative and commutative, and for any value x we have x ^ x = 0 and x ^ 0 = x. Pairwise duplicates cancel each other when XORed together, so after XORing every number only the value that appeared once remains.

A minimal, portable C outline (uses fixed-width unsigned type for portability):

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main(void) {
    uint32_t v, acc = 0;
    while (scanf("%" SCNu32, &v) == 1) {
        acc ^= v;
    }
    printf("%" PRIu32 "\n", acc);
    return 0;
}

Notes and caveats: prefer unsigned types to avoid sign-bit surprises; if inputs can exceed 32 bits use uint64_t and the matching PRIu64/SCNu64 macros. The XOR method only works when all repeats occur exactly twice and only one element is unique; if that condition changes you need other approaches (hash table for arbitrary counts, bit-count-modulo techniques for "appear three times" variants, or the two-unique-numbers partition trick). ’s linked-list idea or a naive index array (as suggested) are either slower or infeasible given the 0..10^9 domain. Finally, I/O parsing will dominate run time for 500k values, so use buffered reads if you need strict sub-second guarantees.

Recommended Answers

All 10 Replies

Member Avatar for Ancient Dragon

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
Member Avatar for Member #957352

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

Member Avatar for shanki himanshu

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

commented: Nice! Didn't know that! +14
Member Avatar for Ancient Dragon

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?

commented: first time, god of C asking a question :D +2
Member Avatar for shanki himanshu

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.

commented: slick :) +14
Member Avatar for WaltP

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
Member Avatar for Ancient Dragon

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
Member Avatar for WaltP

Oops. Missed that...

Member Avatar for Member #957352

i think shanki himanshu has a great solution.

Member Avatar for Ancient Dragon

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.