Количество возможных пар, сумма и побитовое исключающее ИЛИ которых заданы
Даны два целых числа 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)*2The 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)