Algorithms

Search

Find missing item in a list of different items

Given N different items, find in a list of N-1 items, in random order, which one is missing

Solution:

• Assume each item can be represented as a binary element (like 32-bit integer).
• First XOR all N items together, and compute a reference SUM value.
• Second, XOR all N-1 items in the list, and the XOR with the reference SUM value.
• The result is the binary representation of the missing element.

Source: [1] (see comments).