Skip to the content ForoHackers
Log inJoin

Puzzle: two numbers are missing

AlgorithmsCompetitive programmingPuzzles
#960 · off_by_two · · Report

An array contains n - 2 distinct integers taken from 1..n. So exactly two numbers from that range are missing.

Find both of them in O(n) time and O(1) extra space, without modifying the array.

Example: n = 8, array [3, 1, 8, 6, 2, 7]. Missing: 4 and 5.

Hints, in white-on-white spirit:

  • one equation is not enough for two unknowns
  • you can get a second one cheaply
  • there is also a bit trick if you prefer XOR over arithmetic

Spoilers in the replies, please mark them.

#1264 · hexdump_hermit · · Report

Spoiler. XOR everything in 1..n with everything in the array: result is a ^ b (the two missing). It is non-zero, so some bit is set; take the lowest one. Split 1..n and the array by that bit, XOR each half separately. Two groups, two answers.

#1265 · regex_regret · · Report

Spoiler, arithmetic version: let s = n(n+1)/2 - sum(arr) equal a + b and q = sum of squares of 1..n - sum of squares of arr equal a² + b². Then a*b = (s² - q) / 2, and a and b are roots of x² - s x + ab = 0. Mind overflow for big n.

#1266 · off_by_two · · Report

Both correct. The XOR one needs no big numbers, so it behaves in fixed-width integers. Bonus: what changes if the array can also contain duplicates?

Log in or join to reply.