edik_m (edik_m) wrote,
edik_m
edik_m

Category:

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

Случайно наткнулся. Очень подходят для интервью
Задача 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]+…


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


Tags: рабочее, тест
Subscribe

  • Чтение за март

    1)Джон Стейнбек " К востоку от Эдема".Читал Игорь Князев И как эта книга прошла мимо меня? Вряд ли имеет смысл пересказывать эту книгу. Кто читал ,…

  • Чтение за февраль

    1)Грэм Симсион " Триумф Рози". Читал Креминский Дмитрий Если честно, то я не хотел читать эту книгу. На мой вкус "Эффект Рози" (2-я книга) был чуть…

  • Чтение за январь

    1)Фредрик Бакман " Тревожные люди". Читал Кирилл Радциг. Честно сказать, я уже не представляю, что Бакмана читает кто-то другой Новую книгу Бакмана…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments