Проверить, может ли число быть представлено в виде суммы чисел, в которых хотя бы одна цифра равна K

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

Даны целые числа N и K , задача состоит в том, чтобы проверить, может ли число быть представлено в виде суммы чисел, у которых хотя бы одна цифра равна K.

Пример:

Input: N = 68, K = 7
Output: YES
Explanation: 68 = (27 + 17 + 17 + 7). Each number has atleast one digit equal to 7.

Input: N = 23, K = 3
Output: YES
Explanation: 23 itself contains a digit equal to 3.

Подход: Данная проблема может быть решена с помощью простых математических понятий. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную temp значением k , а также возьмите счетчик, например count , присвойте ему значение 0.
  • Итерировать до тех пор, пока последние цифры temp и N не будут равны, и на каждой итерации
    • Увеличьте значение temp на k
    • Ведите подсчет итераций и прерывайте цикл, если количество становится больше 10.
  • Проверьте, равны ли последние цифры temp и N , и если значение temp <= N :
    • Если приведенное выше условие выполнено, верните true
    • В противном случае вернуть ложь
  • Также, если k * 10 <= N , вернуть true
  • В противном случае вернуть ложь

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


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

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