Количество уникальных пар, у которых побитовое 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 pairInput: 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:
- a + b = ( a | b ) + ( a & b )
- 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 = 1Since (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 (2n) & (2n-1)==0, So we can directly count the number of pairs of form 2n and 2n-1.
Ниже приведена реализация вышеупомянутой идеи.
Временная сложность : O(log N), так как вычисляется в log (N) времени.
Космическая сложность: O(1)
Статьи по Теме:
- Побитовые операторы
- Введение в побитовые алгоритмы - учебные пособия по структурам данных и алгоритмам