Минимизируйте операции по уменьшению A и B до 1 путем уменьшения 1 или деления A на B и B на A.

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

Даны два положительных целых числа A и B . Задача состоит в том, чтобы минимизировать операции, необходимые для уменьшения A и B до 1 . Существует два типа операции:

  1. Уменьшите A или B на 1 .
  2. Разделите A на B или B на A или выполните оба деления одновременно, только если остаток от деления равен 0 .

Пример:

Input: A = 13, B = 5
Output: 6
Explanation: Below are the operations performed to reduce A and B to 1.

Initially A = 13, B = 5
Step 1: Decrement A by 1: A = 12, B = 5
Step 2: Decrement B by 1: A = 12, B = 4
Step 3: Divide A by B and assign it to A : A = 3, B = 4
Step 4: Decrement A by 1: A = 2, B = 4
Step 5: Divide B by A and assign it to B : A = 2, B = 2
Step 6: Divide both A by B and B by A, assign it to A and B respectively: A = 1, B = 1
Therefore, total 6 steps required to reduce A and B to 1. Which is minimum possible.

Input: A = 3, B = 27
Output: 3

Подход: Эту проблему можно решить с помощью рекурсии. Создайте рекурсивную переменную и возьмите переменную, скажем, cntOperations = 0 , чтобы отслеживать количество выполненных операций. Для базового условия проверьте, если A=1 и B=1 , затем верните cntOperations , в противном случае проверьте каждую возможную операцию, которую можно выполнить.

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

Временная сложность: O(max(A, B))

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

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