Интересные задачки

[edik_m]

Случайно наткнулся. Очень подходят для интервью
Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

Задача 2. В последовательности записаны целые числа. Одно из чисел встречается ровно один раз, остальные — по два раза. Найти число, которое встречается один раз.

Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся.

Задачка посложнее
Задача 3. В последовательности записаны целые числа. Число X встречается один или два раза, остальные числа — по три раза. Найти число X. Для простоты считаем, что числа неотрицательные.

Поступим аналогично предыдущей задаче: переведём каждое из чисел в троичную систему: b=b[0]+3*b[1]+32*b[2]+… Для каждого разряда найдём сумму его значений по модулю 3 (обозначим суммы s[0],s[1],s[2],...). Кроме того, посчитаем сами числа.
Если чисел в последовательности было 3*k+1, то X встретился один раз, и его значение равно s[0]+3*s[1]+32*s[2]+… Если же чисел было 3*k+2, то в наборе s[i] единицы придётся заменить на двойки и наоборот: x[i]=(3-s[i])%3, и X=x[0]+3*x[1]+32*x[2]+…

Над остальными пока сам думаю, потому и не пишу. Ссылку тоже не даю :)

Comments

[donkihot.livejournal.com]

Потому, что число системе счисления с основанием p записывается как:
X=x[0]+p*x[1]+p^2*x[2]+p^3*x[3]+ ...+ p^i*x[i]+
Т.е. в троичной:
X=x[0]+3*x[1]+3^2*x[2]+…

[edik-m.livejournal.com]

согласен. Но почему 9? у меня 8 :)

[donkihot.livejournal.com]

3^2=9 я имелл ввиду только это.
Там, где у тебя написано 32 (в трех местах) должно быть написано или 9 или 3^2

[edik-m.livejournal.com]

aa-a-a!
спасибо!