Преобразование N в K путем умножения на A или B с минимальными шагами

Даны два числа N и K , а также пара A и B , задача состоит в том, чтобы умножить N на A или B столько раз, чтобы получить K за минимальное количество шагов. Если невозможно получить K из N, вернуть -1 ;

Примеры :

Input: n = 4, k = 5184, a = 2, b = 3
Output: 8
Explanation: 4→12→24→72→144→432→1296→2592→5184

Input: n = 5, k = 13, a = 2, b = 3
Output: -1

Подход : Данную проблему можно решить с помощью рекурсии.

Следуйте инструкциям, чтобы решить эту проблему:

• Инициализировать переменную счетчика, Cnt = 0.
• Вызвать рекурсивную функцию для решения с параметром n, k, a, b, Cnt.
• Проверить, если n == k, вернуть Cnt.
• В противном случае, если n > k, вернуть INT_MAX;
• Call, min(решить(a*n, k, a, b, Cnt + 1), решить(b*n, k, a, b, Cnt + 1)).
• Если возвращаемое значение не равно INT_MAX, то выведите его, иначе выведите -1.

Ниже приведена реализация описанного выше подхода.

Временная сложность : O(2^k)
Вспомогательное пространство : O(2^k)