Проверить, можно ли сделать данные два числа равными или нет, изменив 1 бит или 2 бита один раз

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

• Измените i -й бит числа на 0 или 1
• Измените i -й бит на 0 или 1 в A и j -й бит на 0 или 1 в B

Если возможно сделать числа равными, то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: A = 5, B = 15
Output: Yes
Explanation: The binary representations of the numbers 5 and 15 are 0101 and 1111 respectively. 
Now, change the fourth bit of the number 5 to 1 and the second bit of the number 15 to 0. 
Therefore, both the numbers become equal, i.e. 13.

Input: A = 8, B = 7
Output: No

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

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : если мы предположим, что числа имеют длину всего 32 бита, то временная сложность будет O (1). но числа могут иметь длину N бит ... поэтому временная сложность в этом случае будет O (N).
Вспомогательное пространство : если числа имеют длину N бит, то необходимое пространство будет O (N) для хранения их двоичного представления. Если максимальная длина двоичного представления A и B равна 32, тогда только сложность Space будет O (1).

Эффективный подход: поскольку нам нужно подсчитать количество разных битов в A и B….. Поэтому мы будем использовать здесь свойство XOR и сгенерируем число, которое имеет только набор битов, которые различны в A и B.

поэтому мы сделаем X=A^B, тогда установленными битами в X будут те биты, которые различны в A и B.

Теперь наша работа состоит в том, чтобы подсчитать количество установленных битов в X.

Временная сложность : независимо от того, насколько длинными являются A и B, временная сложность будет O (log (max (A, B))) в худшем случае.

В среднем временная сложность будет O(1), так как нам нужно подсчитать только 2 установленных бита.

Сложность пространства: O(1) Всегда.