AppliedNumeric answer

Finding the unpaired ids · Part 2 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 two ids appear once each: 12, 5, 6, 9, 5, 9. XOR-ing the array gives x, the XOR of the two unknowns, and `x & -x` isolates a bit on which they differ, used to split the array into two groups. What is `x & -x`?

Answer with a number. Fractions, powers and expressions like 23/6 or C(52,5) are read correctly in practice.

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 two ids appear once each: 12, 5, 6, 9, 5, 9. XOR-ing the array gives x, the XOR of the two unknowns, and x & -x isolates a bit on which they differ, used to split the array into two groups. What is x & -x?

More data structures and algorithms questions

Now two ids appear once each: 12, 5, 6, 9, 5, 9. XOR-ing the array gives x, the XOR of the two unknowns, and `x & -x` isolates a bit on which they differ, used to split the array into two groups. What is `x & -x`?