Количество x в заданном диапазоне, таких что побитовое XOR x, (x+1) и (x+2), (x+3) равны

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

Для заданного целого числа N задача состоит в том, чтобы подсчитать количество целых чисел (скажем, x ) в диапазоне [0, 2 N −1] , таких что x⊕(x+1) = (x+2)⊕(x+3) . [где ⊕ представляет собой побитовое исключающее ИЛИ]

Примеры :

Input: N = 1
Output: 1
Explanation: Only 0 is the valid x, as, 0 ⊕ 1 = 2 ⊕ 3 = 1

Input: N = 3
Output: 4

Наивный подход : простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные значения x в диапазоне [0, 2 N −1] и проверить, удовлетворяют ли они заданным критериям, т. е . x⊕(x+1) = (x+ 2)⊕(х+3) .

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Итерация от i = 0 до N .
    • Проверить, если (i ⊕ (i+1)) = ((i+2) ⊕ (i+3))
    • Если условие выполнено, увеличьте количество таких чисел.
  • Верните окончательный счет в качестве ответа.

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

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

Эффективный подход . Задача может быть эффективно решена на основе следующей математической идеи:

  • If x is such that it is a even number then x+2 is also a even number and both (x+1) and (x+3) will be odd numbers. 
  • Now two consecutive even and odd number has only a single bit difference only on their LSB position.
  • So the bitwise XOR of (x and x+1) and (x+2 and x+3) both will be 1, when x is even.
  • Therefore all the even numbers in the given range [0, 2N−1] is a possible value of x.

So total number of such values are (2N – 1)/2 = 2N-1

Следуйте иллюстрации ниже, чтобы лучше представить идею:

Иллюстрация:

Consider N = 3. So the numbers are in range [0, 7]

All even numbers in the range are 0, 2, 4 and 6

=> When x = 0: 0 ⊕ 1 = 1 and 2 ⊕ 3 = 1. Therefore the relation holds
=> When x = 2: 2 ⊕ 3 = 1 and 4 ⊕ 5 = 1. Therefore the relation holds
=> When x = 4. 4 ⊕ 5 = 1 and 6 ⊕ 7 = 1. Therefore the relation holds
=> When x = 6: 6 ⊕ 7 = 1 and 8 ⊕ 9 = 1. Therefore the relation holds.

Now for the odd numbers if it is done:

=> When x = 1: 1 ⊕ 2 = 3 and 3 ⊕ 4 = 7. Therefore the relation does not hold.
=> When x = 3: 3 ⊕ 4 = 7 and 5 ⊕ 6 = 3. Therefore the relation does not hold.
=> When x = 5: 5 ⊕ 6 = 3 and 7 ⊕ 8 = 15. Therefore the relation does not hold.
=> When x = 7: 7 ⊕ 8 = 15 and 9 ⊕ 10 = 3. Therefore the relation does not hold.

So total possible values are 4 = 23-1

Следовательно, чтобы получить ответ, вычислите значение 2 N-1 . для заданного N

Ниже приведена реализация описанного выше подхода.

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

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