Как выполнить поиск количества чисел удовлетворяющих условию в промежутке[x,y]?

Question

[onemantwo]

Доброго времени суток! Есть вот такая задача:
В промежутке [1, 2300000] необходимо найти такие числа, в которых имеется последовательность цифр, дающая в сумме число 10 и при этом, последовательность должна включать в себя число 5.

К примеру 523014 подойдет, а 234187 - нет. Как алгоритмически правильно реализовать задачу? Не хочется строить 2300000 строк и потом анализировать каждую.
Ну или хоть построить исключительно числа содержащие 5 в заданном промежутке.

Comments

[Сергей Соколов]

повторяться цифры могут? 522222 – валидный вариант?

[onemantwo]

Сергей Соколов, вполне, число же входит в промежуток. Однако приведенный вариант невалидный - число 10 путем сложения с применением 5 мы из него не получим. 511111 - валидный.

[Сергей Соколов]

получилось найти элегантное решение?

Answer 1

[Сергей Соколов]

Наверное, надо не искать, а генерить такую последовательность.

Одна из цифр уже обязана быть «5». Для остальных надо собрать все варианты (с учётом порядка) разложения 5 в сумму цифр: от 11111 до 5.

Теперь нужно собрать все варианты размещения пятёрки и каждой из комбинаций, вписывающиеся в диапазон [1 .. 23е5]. Можно рекурсивно набирать слева направо. На первую позицию годятся цифры 0, 1, 2. На вторую при первой "2" 0, 1, 2, 3, или любый при 0 или 1. С третьей по седьмую - любые.

Для каждого варианта набора суммы ещё все варианты положения неучаствующих цифр.

Answer 2

[Wataru]

Ограничения небольшие - проще всего тупо перебрать все числа до 23 миллионов, перевести каждое в число и проверить на соответствие условию. Можно чуть ускорить проверки, если считать сумму цифр и количество '5' в подстроке быстро с помощью частичных сумм (считаете, сумму и количество цифр 5 в каждом префиксе строки. Потом вычитаете из значений для одного префикса значения более короткого - остаются значения для подстроки).