Проверьте, возможно ли построить массив размера N, имеющий сумму как S и значение XOR как X

Даны три числа N, S и X , задача состоит в том, чтобы выяснить, возможно ли построить последовательность A длины N , где каждое A[i] >= 0 для 1<=i<=N и сумма всех чисел в последовательность равна S , а побитовое XOR последовательности равно X .

Примеры:

Input: N = 3, S = 10, X = 4 
Output: Yes
Explanation: One of the sequence possible is {4, 3, 3} where sum equals 10 and XOR equals 4

Input: N = 1, S = 5, X = 3
Output: No

Подход: Давайте рассмотрим следующие тестовые примеры.

Случай 1: когда N равно 1 , легко увидеть, что когда (S равно X) , тогда возвращается только « Да », иначе « Нет ».

Случай 2: когда N больше 3 , используйте формулу (a + b) = (a xor b) + 2(a и b). Здесь видно, что (a + b) = S и (a xor b) = X , поэтому уравнение становится S = X + 2 (ab). Следовательно, (SX) должно быть четным, потому что справа у нас 2(ab). Таким образом, можно сказать, что если S нечетно, то X нечетно, а если S четно, то X четно только тогда, (SX) также четно, что можно проверить с помощью (S%2 == X%2) также S >= X , иначе AB становится отрицательным, что невозможно.

Случай 3: для случая, когда N равно 3, это что-то вроде A + B + C = S и A^B^C = X. Используйте свойство A^A = 0 и 0^A = A => X + ( S – X)/2 + (S – X)/2 = X + (SX) => X + ( S – X)/2 + (S – X)/2 = S и еще так: X ^( ( S – X)/2 ^ (SX)/2 ) = X ^ 0 = X. Следовательно, доказано, что при N == 3 такая последовательность всегда будет и мы можем просто вернуть « Да ».

Случай-4: когда N == 2 и (S%2 == X%2) и S >= X , предположим, что A + B == S и (A^B) == X , тогда ( A и B) == (SX)/2 Из уравнения, рассмотренного выше. Пусть C = AB . При внимательном наблюдении можно заметить, что биты C равны «1» только тогда, когда биты A и B равны «1» для этой позиции и выключены в противном случае. И X, который является xor для A, B имеет бит on только тогда, когда есть разные биты, которые находятся в i ^-й позиции, A имеет «0», а B имеет «1» или прямо противоположное: Итак, глядя на эту последовательность, назначьте каждый бит в переменные A и B, C = (S – X)/2. Назначить A и B из C -> A = C, B = C

Теперь добавьте X в A или B , чтобы назначить все единицы в A и все нули в B , поэтому, когда мы выполняем XOR обоих чисел, добавленные биты «1» в A будут просто противоположны тому, что мы добавили в B, что равно «0». . Самое интересное, что когда установленные биты C совпадают с некоторыми установленными битами X, тогда это не даст желаемого xor для X. Теперь A = C + X, B = C. Теперь A + B = ( C + X) + C = S и когда XOR AB равно X, то можно быть уверенным, что такая пара существует, когда A + B == S и (A^B) == X;

Выполните следующие шаги, чтобы решить проблему:

• Если S больше, чем равно X, а S%2 равно X%2 , выполните следующие действия, иначе верните No.
  • Если n больше, чем равно 3, вернуть Да.
  • Если n равно 1, и если S равно X, вернуть Да , иначе вернуть Нет.
  • Если n равно 2, инициализируйте переменную C как (SX)/2 , установите переменные A и B как C и добавьте значение X к переменной A , и если A^B равно X, то напечатайте Yes , иначе напечатайте No.

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

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