Привет, мир!
Давайте разберемся с проблемой Sum vs XOR на HackerRank. Вы можете щелкнуть заголовок, чтобы прочитать описание проблемы. Итак, начнем.
Здесь вы можете использовать грубую силу для перебора x, 0 ≤ x ≤ n, и если сумма x и n равна XOR или x и n, то увеличивайте счетчик. Это занимает O (n²) времени и неэффективно для больших значений n. Давайте посмотрим более эффективное решение.
Пусть два двоичных числа будут 1010 и 0100. Здесь сумма и XOR двух вышеуказанных чисел равны. Вы здесь что-то заметили? Рассмотрим первое число. Всякий раз, когда в первом числе стоит «1», во втором номере есть соответствующий ноль. Это сделано для того, чтобы избежать переноса и сохранения суммы, равной свойству XOR. Кроме того, всякий раз, когда в первом числе стоит «0», не имеет значения, стоит ли в соответствующей позиции ноль или единица. Результат никогда не приведет к переполнению.
Следовательно, количество чисел меньше числа ’n’, сумма которых и XOR равны, равно 2 ^ (количество нулей). Количество единиц не повлияет, поскольку их значение соответствующей позиции во втором числе будет фиксированным. Все числа, сгенерированные как таковые, будут меньше заданного числа ’n’. Вы можете перепроверить это.
Открыт для предложений. Код этой проблемы на Python3 можно найти здесь.
Удачного кодирования…
