Проверить, может ли число быть представлено в виде суммы чисел, в которых хотя бы одна цифра равна 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)