AdvancedMultiple choice

Finding the unpaired ids · Part 3 of 3

An array holds integer order ids. Unless a part says otherwise, every id appears exactly twice except the ones you are asked to find, and you may use only $O(1)$ extra memory.

Now every id appears three times except one, which appears once. Which method finds it in $O(n)$ time and $O(1)$ memory?

AXOR everything, as before
BFor each of the 64 bit positions, count the ids with that bit set, modulo 3
CSort the array in place with heapsort, then scan for the value that is not repeated three times
DCount occurrences in a hash map

The worked solution is in Premium

The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.

Start the 7-day free trial Practise it with Premium

Learn the method

Bit manipulation and modular arithmetic

Now every id appears three times except one, which appears once. Which method finds it in O(n)O(n)O(n) time and O(1)O(1)O(1) memory?

More data structures and algorithms questions

Now every id appears three times except one, which appears once. Which method finds it in $O(n)$ time and $O(1)$ memory?