Уменьшить число до 1, выполнив заданные операции | Набор 3

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

1. Если число является степенью двойки, то разделить число на 2 .
2. В противном случае вычтите из N наибольшую степень 2, меньшую, чем N .

Примеры:

Input: N = 2 
Output: 1
Explanation: The given number can be reduced to 1 by following the following steps:
Divide the number by 2 as N is a power of 2 which modifies the N to 1.
Therefore, the N can be reduced to 1 in only 1 step.

Input: N = 7 
Output: 2
Explanation: The given number can be reduced to 1 by following the following steps:
Subtract 4 the greatest power of 2 less than N. After the step the N modifies to N = 7-4 = 3.
Subtract 2 the greatest power of 2 less than N. After the step the N modifies to N = 3-2 = 1.
Therefore, the N can be reduced to 1 in 2 steps.

Способ 1 –

Подход: Идея состоит в том, чтобы рекурсивно вычислить минимальное количество необходимых шагов.

• Если число является степенью двойки, то нам разрешено делить число только на 2 .
• В противном случае мы можем вычесть из N наибольшую степень двойки, меньшую, чем N .
• Таким образом, мы будем использовать рекурсию как для операций, когда они действительны, так и для возврата количества операций.

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

Способ 2 –

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

• Инициализируйте две переменные, скажем, res со значением 0 и MSB со значением log ₂ (N) , чтобы сохранить количество шагов, необходимых для уменьшения числа до 1 и старшего бита N .
• Итерировать, пока N не равно 1:
  • Проверьте, является ли число степенью двойки, затем разделите N на 2 .
  • В противном случае вычтите наибольшую степень числа 2 меньше N из N , т.е. обновите N как N=N-2 ^MSB .
  • Увеличьте res на 1 и уменьшите MSB на 1 .
• Наконец, напечатайте res .

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

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