Количество уникальных пар, у которых побитовое XOR и OR совпадают

Учитывая целое число N , задача состоит в том, чтобы найти количество пар (скажем, {a, b} ) от 1 до N (обе включительно), которые удовлетворяют условию:

• a и b — различные элементы.
• Значения | b и a ^ b равны и
• a( a | b ) = b( a ^ b ) – ( a | b ) также верно.

Примеры:

Input: N=5
Output:1
Explanation: If we consider a=3 and b=4, then a | b = 7 and a ^ b=7. Thus it forms a valid pair

Input: N=8
Output: 3 
The possible pairs are  {1, 2}, {3, 4} and {7, 8}

Интуиция:

Let us consider two numbers a and b. As we know, the sum of these two values can be written as:

1. a + b = ( a | b ) + ( a & b )
2. a + b = ( a ^ b )  + 2*( a & b)

So equating 1 and 2 we get:
a | b + (a & b) = a^b + 2 * (a & b) or
a | b = a ^ b + (a & b)  (equation 3)

Since it is said that (a ^ b) = (a | b), from third condition, we can derive:
a * ( a | b ) = b * ( a ^ b ) – ( a | b ) or
a * (a | b) = b * (a | b) – (a | b) or 
a = b – 1 i.e. b – a = 1

Since (a ^ b) and (a | b) are same, so from the 3rd equation we can derive that (a & b) = 0.

So the question finally boils down to figure out the adjacent pair of elements whose bitwise AND is 0.

Наивный подход с использованием линейной итерации:

The basic idea to solve this problem is to store count of unique adjacent pairs by iterating over the array using a loop from 1 to N.

• Инициализируйте переменную-счетчик (скажем, count ), чтобы хранить количество уникальных пар.
• Начните обход, используя от i = 1 до N-1 :
  • Найдите побитовое И для i и i+1 , и если оно равно 0, увеличьте count .
• Возврат счетчика в качестве требуемого ответа.

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

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

Эффективный подход:

Since we know that  both the numbers differ by 1 hence by the property of the AND operation of any power of 2 with a number  that is one less than that gives 0. Hence (2ⁿ) & (2ⁿ-1)==0, So we can directly count the number of pairs of form 2ⁿ and 2ⁿ-1.

Ниже приведена реализация вышеупомянутой идеи.

Временная сложность : O(log N), так как вычисляется в log (N) времени.
Космическая сложность: O(1)

Статьи по Теме:

• Побитовые операторы
• Введение в побитовые алгоритмы - учебные пособия по структурам данных и алгоритмам