You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.
Input
The single line of the input contains a pair of integers m, s (1 ≤ m ≤ 100, 0 ≤ s ≤ 900) — the length and the sum of the digits of the required numbers.
Output
In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1 -1" (without the quotes).
#include <iostream>
usingnamespace std;
int main()
{
int m, s;
int i;
cout << "Input m s (where 1 <= m <= 100, 0 <= s <= 900): ";
cin >> m >> s;
// Deal with impossible case first
if ( s < 1 || s > 9 * m )
{
cout << "-1 -1";
return 0;
}
// Otherwise set up integer array to hold m (possibly 100) digits
int * digits = newint[m];
// Going to build from as many 9s as possible - either to right or left
int nines = s / 9; // number of 9s to use
int remainder = s % 9; // left over
// ===== Minimum: as many 9s as possible to RIGHT =====
for ( i = 0 ; i < m - nines; i++ ) digits[i] = 0;
for ( i = m - nines; i < m ; i++ ) digits[i] = 9;
i = m - nines; // store first non-zero digit
if ( remainder > 0 ) digits[--i] = remainder;
// This may leave the first digit zero, so correct by pinching 1 from first non-zero digit
if ( digits[0] == 0 )
{
digits[0]++;
digits[i]--;
}
for ( i = 0; i < m; i++ ) cout << digits[i];
cout << ' ';
// ===== Maximum: as many 9s as possible to LEFT =====
for ( i = 0 ; i < nines; i++ ) digits[i] = 9;
for ( i = nines; i < m ; i++ ) digits[i] = 0;
if ( remainder > 0 ) digits[nines] = remainder;
for ( i = 0; i < m; i++ ) cout << digits[i];
cout << ' ';
delete [] digits;
}
Input m s (where 1 <= m <= 100, 0 <= s <= 900): 2 15
69 96
Input m s (where 1 <= m <= 100, 0 <= s <= 900): 3 0
-1 -1
Input m s (where 1 <= m <= 100, 0 <= s <= 900): 50 303
10000000000000005999999999999999999999999999999999 99999999999999999999999999999999960000000000000000
What remainder is that exactly the remainder of what? I mean for the first example its 6 I get it but what does the "remainder" refer to, like the nines is the number of 9s we need but what about the remainder?
You have to get the sum right - it won't usually be a whole number of 9's and the remainder is what is left. % is the modulo operation and here gives the remainder when sum s is divided by 9.
E.g when s = 15.
s/9 gives 1 (by integer division). s % 9 gives 6. So you have one 9 and the 6.
The minimum is 69 and the maximum is 96.
What if we consider an input sample for m = 3, s = 20
The s/9 is 2 and s%9 is 2, so I have 2 9s and and a 2?
If that's valid then where did this entire operation come from? Like how did you know that dividing by 9 would get you the 9s you need and then %9 would get you the value that sticks to the 9 either left or right depending on min or max. I am confused on how I am supposed to come up with such equations like is that something related to number theory / maths? like if you've got a value and you want to get such values that add up and reach that value you just /9 for the 9s and %9 for the number that sticks to it from left or right?
For the minimum possible value you want small digits (0) at the front (because any numbers here would have high values) and large digits (9) at the back (because the numbers here, 1's, 10's etc, would have relatively low values). The opposite would be true for the maximum value. Unless s is itself a multiple of 9, there must be a number smaller than 9 left over when you have removed as many 9s as possible.
Suppose you sum s is 20 (your example). How many 9's can you fit in there?
20/9 = 2.something ... but integer division: int nines = 20 / 9;
would give 2.
Once you have taken away both those 9s from 20 then you still have 2 left over. The code int remainder = 20 % 9;
will you give you this remainder - look up "modulo" on a school maths site if you need to. In c++, % is the modulo operator.
If I want the minimum number then I put all my 9s to the right and then the remainder just in front of them. (There is a minor Trump in the works here as the first digit mustn't be zero - so I do some borrowing: see my code.)
If I want the maximum number then I put all the 9s on the left (the high-value placements) and the remainder just after them.
Remember that our numbering system works something like
... thousands - hundreds - tens - units
so if you want big numbers you will keep your supply of digits to the left (each worth 1000 say) and if you want small numbers you will keep them to the right (each worth 1 say).
Thank you @lastchance this one was 100% detailed. appreciate your effort <3
PS: I definitely know what the % is xD that's basic maths haha I just didn't figure out that it was supposed to mean the remaining digit after TAKING x 9s from the sum.