Количество целых чисел K в диапазоне [0, N], таких что (K XOR K+1) равно (K+2 XOR K+3)

Опубликовано: 22 Сентября, 2022

Учитывая целое число N , задача состоит в том, чтобы напечатать количество всех неотрицательных целых чисел K , меньших или равных N, так что побитовое XOR для K и K+1 равно побитовому XOR для K+2 и K+3 .

Примеры:

Input: N = 3
Output: 2
Explanation: 
The numbers satisfying the conditions are:

  1. K = 0, the bitwise XOR of 0 and 1 is equal to 1 and the bitwise xor of 2 and 3 is also equal to 1.
  2. K = 2, the bitwise XOR of 2 and 3 is equal to 1 and the bitwise xor of 4 and 5 is also equal to 1.

Therefore, there are 2 numbers satisfying the condition.

Input: 4
Output: 3

Наивный подход: самый простой подход — перебрать диапазон [0, N] и проверить, удовлетворяет ли текущее число условию или нет. Если он удовлетворяет, увеличьте счетчик на 1 . После проверки всех чисел выведите значение счетчика.

Временная сложность: O(N)
Вспомогательное пространство: O(1)

Эффективный подход. Приведенный выше подход можно оптимизировать, заметив, что все четные числа в диапазоне [0, N] удовлетворяют заданному условию.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ