Print Minimum and Maximum n-digit numbers whose sum of digits equals to given sum

[Shervan360]

Hello,

I would like to print the minimum and maximum n-digit numbers whose sum of digits equals to given sum.

1<=m<=100
0<=s<=900

for example:
2 15
result:
69 96

3 0
result:
-1 -1

If the program doesn't have any result, print -1 -1

I wrote the below program but it doesn't work for big m and s. for example: for m =100 and s = 900

  #include <stdio.h>
#include <math.h>

int  Sum(int num)
{
	int s = 0;
	while (num > 0)
	{
		s += num % 10;
		num /= 10;
	}
	return s;
}

int main()
{
	int n, m;
	int min = -1, max = -1;
	int flagMin = 0;
	int flagMax = 0;

	scanf("%d", &m);
	scanf("%d", &n);

	for (int i = pow(10,m-1); i < pow(10, m ); i++)
	{
		if (n == Sum(i))
		{
			if (flagMin == 0)
			{
				min = i;
				flagMin = 1;
			}
				max = i;
				flagMax = 1;
		}
	}
	printf("%d %d",min,max);

	return 0;
}

[Ganado]

Assuming you mean m-digit number, indeed you are trying to calculate numbers that go well beyond the capacity of a 32-bit integer. pow(10, 100), for instance, would take 333 bits to be stored as an integer.

Not to mention... there are 9 * 10^99 digits between 10^99 and 10^100. Doing some rough math, even if you iterate over a billion digits (edit:) numbers per second... that would still take approximately a bajillion years to complete.

You will need to change your approach, and use arrays of individual digits or characters.
This sound like a Project Euler question, is that right?

[Shervan360]

@Ganado , Thank you.

You are right, but there is no solution
Running the program takes a long time and we have a time limit.

Please see:

https://i.ibb.co/41b9DYs/Screenshot-2021-01-08-205813.jpg

[dutch]

I calculate that at a trillion numbers per second it would take about 285192790326260552133242071640428929956650695870408396075747205110654802646589094 years.
Better put the coffee on.

[Ganado]

@Shervan,
Yes, like I said, it would take longer than the age of the universe to complete with your current method, even if you could store 333-bit numbers :)

I didn't actually attempt this, but you need to be smarter about how you iterate through the numbers. For an m-digit number, you can't sum to anything over 9 * m. You're going to need some way to severely reduce the search space you're iterating over.

For your example, with m = 100, sum = 900, the answer is actually trivial unless I'm misunderstanding, since a 100-digit number that's all 9s would have a sum of 900, and that's the only number that works since any number lower than that won't have digits that add up to 900. So both your upper bound and lower bound is the number with 100 '9's.

The actual location of the digits don't matter for determining the sum, but do matter for determining whether or not it's the largest or smallest digit. For example, if you are trying to sum to 20, and you are working within 4 digits... 20 = 9 + 9 + 2 + 0. So you have {9, 9, 2, 0}, and if you sort then, you get {0, 2, 9, 9} as the lower bound, and {9, 9, 2, 0} as the upper bound. Try to generalize this.

<Edit: After coming back to this, I realize that decimal 0299 is not a 4-digit number by most definitions...>

[dutch]

Don't use integers. Use a string, or maybe an int array (100 ints).

Consider m = 30, s = 137

Starting with
100000000000000000000000000000
How many 9's can we use? (137-1)/9 = 15 remainder 1
So the minimum answer is:
100000000000001999999999999999
(15 9's in the lowest positions and a 1 in the next lowest position.)
In some cases you will need to increase the initial 1, also.

One way to get the max is to reverse the digits:
999999999999999100000000000001
Then move the lower digits as high up as they can go (add the lowest 1 to the next highest position it can add to)
999999999999999200000000000000

Alternatively for the max, you would start with
999999999999999999999999999999
Sum of digits is 270 so we need to remove 270 - 137 = 133
9's that can be "zeroed" is 133/9 = 14 remainder 7
999999999999999200000000000000
(I removed the 14 lowest-order 9's and subtracted 7 from the lowest-order remaining 9.)

EDIT: I have a working solution now. It's pretty easy, actually.

[Ganado]

The maximum number is the easier part. I just realized that for the minimum number, my solution of {0 2 9 9} for m = 4, s = 20 is wrong since 299 is not a 4-digit number by most definitions. So the lowest 4-digit number would then have to split the 2 into 1s, {1 1 9 9}. (and in general, {1 0 ... 0 {r} 9 ... 9} .) Don't post your solution, I'm just curious if your code accounts for this? It's a pretty simple fix, I should be able to fix my program to account for it as well.

[dutch]

Yes, it accounts for that. I ended up not representing the number at all (as a string or array). It just uses loops and conditions.

[seeplus]

for (int i = pow(10,m-1); i < pow(10, m ); i++)

Won't reduce the time sufficiently, but pow() is an expensive function - and m doesn't change within the loop.

for (int i = pow(10, m - 1), large = pow(10, m); i < large; ++i)

[lastchance]

Some tests (feel free to add some more cases):

#include <iostream>
#include <string>
using namespace std;


void lim( int n, int sum, string &mn, string &mx )
{
   // Code goes here
   // .....
}


int main()
{
   struct Test{ int n, sum; };
   Test tests[] = { { 1, 0 }, { 2, 0 }, { 1, 1 }, { 1, 5 }, { 1, 9 }, { 2, 15 }, { 2, 18 }, { 2, 19 }, { 3, 10 }, { 99, 900 }, { 100, 900 }, { 50, 99 } };

   for ( Test t : tests ) 
   {
      string mn, mx;
      lim( t.n, t.sum, mn, mx );
      cout << "n = " << t.n << "    sum = " << t.sum << "    minimum = " << mn << "    maximum = " << mx << '\n';
   }
}

n = 1    sum = 0    minimum = 0    maximum = 0
n = 2    sum = 0    minimum = -1    maximum = -1
n = 1    sum = 1    minimum = 1    maximum = 1
n = 1    sum = 5    minimum = 5    maximum = 5
n = 1    sum = 9    minimum = 9    maximum = 9
n = 2    sum = 15    minimum = 69    maximum = 96
n = 2    sum = 18    minimum = 99    maximum = 99
n = 2    sum = 19    minimum = -1    maximum = -1
n = 3    sum = 10    minimum = 109    maximum = 910
n = 99    sum = 900    minimum = -1    maximum = -1
n = 100    sum = 900    minimum = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999    maximum = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
n = 50    sum = 99    minimum = 10000000000000000000000000000000000000089999999999    maximum = 99999999999000000000000000000000000000000000000000

[oggin]

My try;

#include <string>
#include<iostream>
#include<vector>
using namespace std;


int sum(const string &s,const int &n)
{
	int acc=0;
	for(int i=0;i<s.size();i++)
	{
		acc+=(s[i]-48);
		if(acc>n) return 0;
}
if(acc<n) return 0;
return 1;
}


void inc(string &s)
{
	string t;
    int counts;
    int ls=s.size();
    while (ls)
    {
        if  (s[ls-counts-1]==57) 
        {
           counts+=1;
            t.resize(ls,'0');
            if (counts==ls) {s="1"+t;return ;}
        }
        else
        {
        	t.resize(counts,'0');
            s=s.substr(0,ls-counts-1)+to_string(s[ls-counts-1]-47)+t;
            return ;
        }       
}
}

int main()
{
	vector<string>v;
	string g="0";
	for(int i=0;i<100;i++)
	{
		inc(g);
		if(sum(g,15)) v.push_back(g);
	
}
cout<<endl;
cout<<"0 to "<<g<<" sum 15"<<endl;
cout<<v[0]<<","<<v[v.size()-1]<<endl;;
cout<<"Please wait . . ."<<endl;

g="100000000000000000000000000000";
string start=g;
v.clear();
for(int i=0;i<2000000;i++)
	{
		inc(g);
		if(sum(g,45)) v.push_back(g);	
}
cout<<endl;
cout<<start<<" to "<<g<<" sum 45"<<endl;
cout<<v[0]<<","<<v[v.size()-1]<<endl;
system("pause");

}