Преобразование N в K путем умножения на A или B с минимальными шагами
Опубликовано: 27 Февраля, 2023
Даны два числа 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→5184Input: 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)