CODEWITHSUNDEEP
algorithm
shreyasva
shreyasva

Reputation: 13456

Finding a number that repeats even no of times where all the other numbers repeat odd no of times

Given is an array of integers. Each number in the array repeats an ODD number of times, but only 1 number is repeated for an EVEN number of times. Find that number.

I was thinking a hash map, with each element's count. It requires O(n) space. Is there a better way?

Upvotes: 7

Views: 4035

Answers (5)

Myna
Myna

Reputation: 559

Apparently there is a solution in O(n) time and O(1) space, since it was asked at a software engineer company with this constraint explictly. See here : Bing interview question -- it seems to be doable using XOR over numbers in the array. Good luck ! :)

Upvotes: 0

Aleks G
Aleks G

Reputation: 57316

You don't need to keep the number of times each element is found - just whether it's even or odd number of time - so you should be ok with 1 bit for each element. Start with 0 for each element, then flip the corresponding bit when you encounter the element. Next time you encounter it, flip the bit again. At the end, just check which bit is 1.

Upvotes: 3

wildplasser
wildplasser

Reputation: 44250

I don't know what the intended meaning of "repeat" is, but if there is an even number of occurrences of (all-1) numbers, and an odd number of occurances for only one number, then XOR should do the trick.

Upvotes: 3

smci
smci

Reputation: 33950

Hash-map is fine, but all you need to store is each element's count modulo 2. All of those will end up being 1 (odd) except for the 0 (even) -count element.

(As Aleks G says you don't need to use arithmetic (count++ %2), only xor (count ^= 0x1); although any compiler will optimize that anyway.)

Upvotes: 3

Saeed Amiri
Saeed Amiri

Reputation: 22555

If all numbers are repeated even times and one number repeats odd times, if you XOR all of the numbers, the odd count repeated number can be found.

By your current statement I think hashmap is good idea, but I'll think about it to find a better way. (I say this for positive integers.)

Upvotes: 1

Related Questions