Algorithms

From miki
Revision as of 15:07, 13 October 2018 by Mip (talk | contribs) (Created page with "== 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: * A...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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).