Минимальное уменьшение или деление на правильный делитель, необходимое для уменьшения N до 1
Для заданного положительного целого числа N задача состоит в том, чтобы найти минимальное количество операций, необходимых для уменьшения N до 1 путем многократного деления N на его собственные делители или путем уменьшения N на 1 .
Примеры:
Input: N = 9
Output: 3
Explanation:
The proper divisors of N(= 9) are {1, 3}. Following operations are performed to reduced N to 1:
Operation 1: Divide N(= 9) by 3(which is a proper divisor of N(= 9) modifies the value of N to 9/3 = 1.
Operation 2: Decrementing the value of N(= 3) by 1 modifies the value of N to 3 – 1 = 2.
Operation 3: Decrementing the value of N(= 2) by 1 modifies the value of N to 2 – 1 = 1.
Therefore, the total number of operations required is 3.Input: N = 4
Output: 2
Подход: Данная проблема может быть решена на основе следующих наблюдений:
- Если значение N четное, то его можно уменьшить до значения 2 , разделив N на N/2 с последующим уменьшением 2 до 1 . Следовательно, минимальное количество необходимых шагов равно 2 .
- В противном случае значение N можно выровнять, уменьшив его, и уменьшить до 1 , используя описанные выше шаги.
Следуйте инструкциям ниже, чтобы решить проблему
- Инициализируйте переменную, скажем, cnt как 0 , чтобы сохранить минимальное количество шагов, необходимых для уменьшения N до 1 .
- Повторяйте цикл, пока N не уменьшится до 1 , и выполните следующие шаги:
- Если значение N равно 2 или N нечетно, то обновите значение N = N – 1 и увеличьте cnt на 1 .
- В противном случае обновите значение N = N/(N/2) и увеличьте cnt на 1.
- После выполнения вышеуказанных шагов выведите в качестве результата значение cnt .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(1)
Вспомогательное пространство: O(1)