Найдите наименьшее число с заданными цифрами и суммой цифр

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

Даны два положительных целых числа 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 , будет наиболее оптимальным выбором. Ниже приведены шаги для описанного выше подхода:

  1. Инициализируйте count_P и count_Q как 0.
  2. Если N делится на P , count_P = N/P и N=0 .
  3. Если N не делится на P , вычтите Q из N и увеличьте count_Q на 1.
  4. Повторяйте шаги 2 и 3, пока N не станет больше 0.
  5. Если N != 0 , невозможно сгенерировать целое число, удовлетворяющее требуемым условиям. В противном случае результирующее целое число будет равно count_Q, умноженному на Q , за которым следует count_P, умноженное на P.

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

Временная сложность: O(N)
Космическая сложность: O(1)

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