Data structures and algorithms
Finding the unpaired ids, part 2 of 3
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 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.
Report an issue with this question
Learn the method
More data structures and algorithms questions
- How many iterations does the loop while (x) { x &= x - 1; n++; } make on x = 255?Applied · Premium
- What is 1oplus2oplus3oplus⋯oplus10, where oplus is bitwise XOR?Applied · Premium
- Computing x¹³ by binary exponentiation (repeated squaring), how many…Applied · Premium
- How many set bits does the integer 90 have?Foundation · Premium
- For a positive integer x, which test is true exactly when x is a power of two?Foundation · Premium
- You need the 100 largest values from a stream of 10⁹ numbers you cannot store.Foundation · Free solution