Количество целых чисел в заданном диапазоне, состоящем только из заданного набора цифр

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

Даны два целых числа L и R и массив arr[] , содержащий однозначные целые числа, задача состоит в том, чтобы найти все целые числа в диапазоне [L, R), состоящем из цифр из заданного массива цифр.

Примеры:

Input: L = 1, R = 100, arr[] = {2, 3, 5, 7}
Output: 20
Explanation: The number between 1 and 100 total integers which are made up with 2, 3, 5, 7 are:
2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, and 77. Total 20.

Input: L = 50, R = 60, arr[] = 5
Output: 1
Explanation: The only number in range 50 and 60 55.

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

Traverse each integer in range [L, R) and check if it consists of only given set of digits. 

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

  • Перебрать диапазон [L, R) .
  • Проверить, является ли число комбинацией чисел, заданных в arr[] или нет, с помощью множества.
  • Если это подмножество заданных цифр, увеличьте количество на 1, иначе нет.

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


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

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