Минимизируйте шаги, чтобы сделать два целых числа равными, увеличив их или выполнив побитовое ИЛИ из них

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

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

  • А = А + 1 (увеличение а на 1).
  • B = B + 1 (увеличить b на 1).
  • А = А | B (замените A побитовым ИЛИ A и B).

Примеры :

Input: A = 5, B = 9
Output: 4
Explanation: It is better to use first operation i.e increase A by 1 four times, 
Input: A = 2, B = 5
Output: 2
Explanation: It is better to apply second operation then third operation,

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

Интуиция:

  • Try to increase A or B by 1, the steps will be the maximum steps possible.
  • Now to reduce these steps,
    • We need to find an intermediate number X such that X OR B = B, because only then we can jump more than 1 number in a single step.
    • Once we have found possible values for X, we can check that which value among them is reachable for A in least steps.
    • Those least steps + 1 step (for doing bitwise OR of X with B) will be one of the lesser number of steps for A to reach B.
  • Another way to reduce these steps:
    • Consider the case when instead of making X OR B = B, we find possible values of Y such that A OR Y = Y, as B can also be moved as per given problem.
    • So we can find least step needed to move B to Y and then add 1 more step to do bitwise OR of A with B.
  • Now try to find the minimum among the both possible lesser steps as the required number of steps to change A to B.

Иллюстрация:

Suppose A = 2, B = 5

Case 1: Possible value of X such that (X OR B = B) => [0, 1, 4, 5]
    Now the steps required to convert A to B if we convert A to each possible value of X first, are:
        Convert A to 0  => not possible as we cannot decrement A 
        Convert A to 1  => not possible as we cannot decrement A 
        Convert A to 4  => 2 increment operation, and then 1 operation for 4 OR 5 to make A as 5. Hence total operation = 3
        Convert A to 5  => 3 increment operation to make A as 5. Hence total operation = 3
Case 2: Possible value of Y such that (A OR Y = Y) => [2, 6, 7, …]
    Now the steps required to convert A to B if we convert B to each possible value of Y first, are:
        Convert B to 2  => not possible as we cannot decrement B 
        Convert B to 6  => 1 increment operation, and then 1 operation for 2 OR 6 to make A as 6. Hence total operation = 2
        Convert B to 7  => 2 increment operation, and then 1 operation for 2 OR 7 to make A as 7. Hence total operation = 3
        Similarly for any conversion of B to value greater than 7 will take more steps. 

Therefore the least steps required to convert A to B using given operations =  min(3, 2) = 2 steps.

Выполните шаги, указанные ниже, чтобы реализовать подход:

  • Перейдите от i = A к B и проверьте, совпадает ли ( i | B ) с B , и шаги, необходимые для этого.
  • Найдите минимальные шаги (скажем, x ), необходимые для того, чтобы сделать A и B равными таким образом.
  • Теперь выполните итерацию для j = B до B+x :
    • Проверьте, удовлетворяет ли это j случаю 2, как указано выше.
    • Обновите минимальные шаги, необходимые для того, чтобы сделать A и B равными.
  • Возвращает минимальное количество шагов.

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

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

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