Найдите наименьшее число с заданными цифрами и суммой цифр
Даны два положительных целых числа P и Q , найдите минимальное целое число, содержащее только цифры P и Q такое, что сумма цифр целого числа равна N .
Пример:
Input: N = 11, P = 4, Q = 7
Output: 47
Explanation: There are two possible integers that can be formed from 4 and 7 such that their sum is 11 i.e. 47 and 74. Since we need to find the minimum possible value, 47 is the required answer.Input: N = 11, P = 9, Q = 7
Output: Not Possible
Explanation: It is not possible to create an integer using digits 7 and 9 such that their sum is 11.
Эффективный подход. Предположим, что P больше или равно Q , count_P обозначает количество вхождений P , а count_Q обозначает количество вхождений Q в результирующем целом числе. Итак, вопрос можно представить в виде уравнения ( P * count_P) + (Q * count_Q) = N , и чтобы минимизировать количество цифр в результирующем целом числе count_P + count_Q должно быть как можно меньше. Можно заметить, что, поскольку P >= Q , максимально возможное значение count_P , удовлетворяющее ( P * count_P) + (Q * count_Q) = N , будет наиболее оптимальным выбором. Ниже приведены шаги для описанного выше подхода:
- Инициализируйте count_P и count_Q как 0.
- Если N делится на P , count_P = N/P и N=0 .
- Если N не делится на P , вычтите Q из N и увеличьте count_Q на 1.
- Повторяйте шаги 2 и 3, пока N не станет больше 0.
- Если N != 0 , невозможно сгенерировать целое число, удовлетворяющее требуемым условиям. В противном случае результирующее целое число будет равно count_Q, умноженному на Q , за которым следует count_P, умноженное на P.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Космическая сложность: O(1)