Другие люди указали на тривиальное решение: переберите все числа от 1 до A. Но эта проблема, на самом деле, может быть решена в почти постоянное время: O(length of A), что составляет O(log(A)).
- Код предоставлен для базы 10. Адаптировать его для произвольной базы тривиально.
- Чтобы достичь вышеупомянутой оценки времени, вам нужно добавить запоминание к рекурсии. Дайте мне знать, если у вас есть вопросы по этой части.
Теперь рекурсивная функция. Написано на Java, но все должно работать на C # / C ++ без каких-либо изменений. Он большой, но в основном из-за комментариев, в которых я пытаюсь уточнить алгоритм.
// returns amount of numbers strictly less than 'num' with sum of digits 'sum'
// pay attention to word 'strictly'
int count(int num, int sum) {
// no numbers with negative sum of digits
if (sum < 0) {
return 0;
}
int result = 0;
// imagine, 'num' == 1234
// let's check numbers 1233, 1232, 1231, 1230 manually
while (num % 10 > 0) {
--num;
// check if current number is good
if (sumOfDigits(num) == sum) {
// one more result
++result;
}
}
if (num == 0) {
// zero reached, no more numbers to check
return result;
}
num /= 10;
// Using example above (1234), now we're left with numbers
// strictly less than 1230 to check (1..1229)
// It means, any number less than 123 with arbitrary digit appended to the right
// E.g., if this digit in the right (last digit) is 3,
// then sum of the other digits must be "sum - 3"
// and we need to add to result 'count(123, sum - 3)'
// let's iterate over all possible values of last digit
for (int digit = 0; digit < 10; ++digit) {
result += count(num, sum - digit);
}
return result;
}
Вспомогательная функция
// returns sum of digits, plain and simple
int sumOfDigits(int x) {
int result = 0;
while (x > 0) {
result += x % 10;
x /= 10;
}
return result;
}
Теперь давайте напишем небольшой тестер
int A = 12345;
int C = 13;
// recursive solution
System.out.println(count(A + 1, C));
// brute-force solution
int total = 0;
for (int i = 1; i <= A; ++i) {
if (sumOfDigits(i) == C) {
++total;
}
}
System.out.println(total);
Вы можете написать более полный тестер, проверяющий все значения A, но общее решение кажется правильным. (Я попробовал несколько случайных А и С.)
Не забывайте, вы не можете протестировать решение для A == 1000000000 без запоминания: оно будет работать слишком долго. Но с запоминанием вы можете проверить это даже для A == 10^1000.
редактировать
Просто чтобы доказать концепцию, запоминание бедного человека. (в Java, в других языках хеш-таблицы объявляются по-разному) Но если вы хотите чему-то научиться, лучше попробовать сделать это самостоятельно.
// hold values here
private Map<String, Integer> mem;
int count(int num, int sum) {
// no numbers with negative sum of digits
if (sum < 0) {
return 0;
}
String key = num + " " + sum;
if (mem.containsKey(key)) {
return mem.get(key);
}
// ...
// continue as above...
// ...
mem.put(key, result);
return result;
}