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?

  • $\begingroup$ Generating functions? $\endgroup$ – Dhaivat Pandya Dec 1 '13 at 6:56
  • $\begingroup$ Well, you can skip all numbers in the set {$710,000,999,999$} $\endgroup$ – user99680 Dec 1 '13 at 7:02
  • $\begingroup$ @user99680, pardon, I can't understand! $\endgroup$ – Silent Dec 1 '13 at 7:05
  • $\begingroup$ @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. $\endgroup$ – user99680 Dec 1 '13 at 7:08
  • $\begingroup$ 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} $\endgroup$ – 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]


C++ program for your problem:

#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)



cout < < count< < endl;

return 0;


int sum (int x){

int add=0;



return add; }


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.