# How many natural numbers less than $10^8$ are there, whose sum of digits equals $7$?

How many natural numbers less than $10^8$ are there, whose sum of digits equals $7$?

I got it here.But is there any more effecient and easier way to solve than the link shows?

• Generating functions? – Dhaivat Pandya Dec 1 '13 at 6:56
• Well, you can skip all numbers in the set {$710,000,999,999$} – user99680 Dec 1 '13 at 7:02
• @user99680, pardon, I can't understand! – Silent Dec 1 '13 at 7:05
• @Sush: Just saying that the sum of digits of numbers in this set, together with the set {$7.100.000, 7.100.001,...., 9.999.999$} will be larger than $8$. Sorry, I should have used dots and commas, to avoid confusion. Maybe this will make the search a bit easier. – user99680 Dec 1 '13 at 7:08
• you can skip all numbers in the set {710,000,999,999} you mean to skip these 4 numbers only? Out of 10^8, why is skipping 4 numbers is important? And a mathematical set can not have duplicate values in it. So your set should be {710,000,999} – Nasser Dec 1 '13 at 7:09

The numbers have 8 places (some of which might be zero), and there are 7 units of value to go into them. (Each place can have at most 9 units, but that's automatic since there's only 7 units total.) So it's a stars and bars problem with 7 stars and 7 bars, making $\binom{14}{7} = 3432$ such numbers.

(For example, |**|*|***|||*| would correspond to the number 02130010.)

[edited: 8 places, not 7]

#include < iostream>

using namespace std;

int main() {

int count=0;

int sum(int x);

for (int i=1;i<100000000;i++){

if (sum(i)==7)

count++;


}

cout < < count< < endl;

return 0;

}

int sum (int x){

while(x){