Забавные задачки

[axm2017]

Часто возникает во всяких обучалках программированию и Ко задача вычисления цифрового корня.
Красивое решение на мой взгляд.
https://codeforces.com/blog/entry/18286

Кто любит в загадки может перед этим поискать решение сам
Цифровой корень натурального числа — это цифра, полученная в результате итеративного процесса суммирования цифр, на каждой итерации которого для подсчета суммы цифр берут результат, полученный на предыдущей итерации. Этот процесс повторяется до тех пор, пока не будет получена одна цифра.
Например цифровой корень 65,536 это 7, потому что 6 + 5 + 5 + 3 + 6 = 25 и 2 + 5 = 7.

[Товарищ ♂uatr]

У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.

[axm2017]

зы решая для ребенка что то из информатики обнаружил неочевидное для себя что Python из коробки может возводить числа в мега степени без проблем. Размерность числа не имеет явного ограничения.
"В Питоне для работы со сколь угодно большими числами надо испольозвать тип «bignum». В Python 2.5+ этот тип называется long и отличается от типа int, но интерпретатор автоматически будет использовать тот, который более подходит."

[axm2017]

Цитата:

Сообщение от Товарищ ♂uatr

У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.

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

[axm2017]

Цитата:

Сообщение от Товарищ ♂uatr

У Яндекса ранее была задачка: найти массиве, состоящем из нечетного количества элементов, уникальное число за время О(n). В рамках условия гарантируется, что только искомое число не имеет парного повторения. Т.е. [1,1,-1,-1,5]. Искомым числом здесь будет 5.

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