Количество возможных пар, сумма и побитовое исключающее ИЛИ которых заданы

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

Даны два целых числа S и X , представляющие сумму и побитовое исключающее ИЛИ соответственно двух целых чисел, задача состоит в том, чтобы найти количество всех таких возможных пар, таких, что их сумма равна S , а побитовое исключающее ИЛИ равно X.

Примеры:

Input: S = 9, X = 5
Output: 4
Explanation: (2, 7), (3, 6), (6, 3), (7, 2) completely satisfies the given conditions.
It can also be seen that no other pair satisfy the given condition.
So the total possibility is 4.

Input: S = 3, X = 3
Output: 4
Explanation: Only (1, 2), (2, 1), (3, 0) and (0, 3) satisfy the given condition.

Подход: Решение задачи основано на следующем наблюдении:

Consider two numbers a and b. Their sum can be written as
a+b = (a XOR b) + (a AND b)*2

The above can be proved as follows:
If two bits x and y are added, the carry (say c) will be (x AND y) and it is to one position left of the single bit. So, c = 2 * (x AND y)
The value of the rightmost bit (i.e., at the same position as of the single bits) will be (x XOR y)
Therefore x + y = (x XOR y) + 2 * (x AND y)

So when adding a and b, this procedure repeats for each bit. Therefore it can be said that the sum will be 
a+b = (a XOR b) + (a AND b)*2 
S = X + 2*A   where A is the bitwise AND of the two numbers.
A = (S – X)/2

Основываясь на приведенном выше наблюдении, количество может быть получено из битовых значений A и X в следующем случае.

  • If the ith bit of X and A both are 0, then there is only one possible pair for that bit position.
  • If the ith bit of X is 1 and of A is 0, then there are two possible pairs for that bit position.
  • If the ith bit of X is 0 and of A is 1, then there is only one possible pair for that bit position.
  • There cannot be a situation where ith bit at X is 1 and ith bit of A is also 1.

Согласно принципу умножения перестановки, чтобы получить количество возможных пар, удовлетворяющих заданному условию, просто перемножьте все возможности. Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Найдите побитовое И двух чисел, используя приведенную выше формулу.
  • Если это не целое число, то решения не существует
  • В противном случае для заданного значения XOR ( X ) и AND (скажем, A ) проверьте каждый бит
    • Найдите количество возможностей для этого бита, используя приведенные выше случаи.
    • Умножьте эти возможности на окончательный ответ.
  • В конце концов, общее количество возможностей, рассчитанное в соответствии с вышеуказанными условиями, является требуемым ответом.

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

Временная сложность: O(N), где N — количество битов в заданной сумме S.
Вспомогательное пространство: O(1)

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