Saltar al contenido ForoHackers

Puzzle: two numbers are missing

AlgoritmosProgramación competitivaAcertijos
#960 · off_by_two · · Denunciar

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 · · Denunciar

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 · · Denunciar

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 · · Denunciar

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?

Inicia sesión o únete para responder.