Минимальный размер массива, возможный с заданными значениями суммы и произведения

Для заданных двух положительных целых чисел S и P задача состоит в том, чтобы найти минимально возможный размер массива, при котором сумма элементов равна S , а произведение элементов равно P. Если такого массива не существует, то выведите «-1» .

Примеры:

Input: S = 5, P = 6
Output: 2
Explanation: The valid array can be {2, 3}, which is of minimum size.

Input: S = 5, P = 100
Output: -1

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Используя N чисел, можно составить массив из размер N имеющий сумму S .
• Любые значения продукта могут быть достигнуты, когда значение P находится между [0, (S/N) ^N ] .

Выполните следующие шаги, чтобы решить данную проблему:

• Сначала проверьте, совпадают ли значения S и P , затем верните 1, так как само значение S используется для создания массива минимального размера.
• Выполните итерацию по диапазону [2, S], используя переменную i , и если значение (S/i) >= pow(P, 1/i), то выведите значение i как результирующий минимальный размер сформированного массива.
• После выполнения вышеуказанных шагов, если нет ни одного возможного значения i , удовлетворяющего вышеуказанным критериям, выведите «-1» .

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

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