How to solve Given Length and Sum of Digits problem in codeforces?

general
1

Please tell me - How to solve Given Length and Sum of Digits problem in codeforces?

2 Likes
2

Firstly check whether the sum is lying between 1 and 9*(length of numbers), if not print “-1 -1” straightforward else you need to distribute the sum such that the digits are descending(left to right) for maximum number and for minimum number distribute the digits in ascending fashion(left to right) to get minimal number, again keep in mind the boundation of max sum obviously following greedy approach.
So basically problem breaks down to the distribution of digits. :slight_smile:
I hope that helps !

3 Likes
3

I am going to explain by taking this solution as reference:

Maximum sum we can form with a number of length m is 9*m(by placing all nines)

so if s is greater than 9*m there is no answer.

Now to find minimum number:

he is traversing from i=m-1 to i=0 and filling every digit.

if i=m-1 then he is filling 1st digit and (m-1) digits are remaining (excluding present digit).

if i=m-2 then he is filling 2nd digit and (m-2) digits are remaining(excluding present digit).

so if he is at some i then i digits are remaining.

Maximum possible sum we can form with those remaining i digits is 9*i and k is the remaining sum.

hence j=max(0,k-9*i)

he is assigning 1 to j if i==m-1 and j==0 because we should not have leading zeroes.

and he is taking j at that place and subtracting j from remaining sum k.

Now to find maximum number:

first we take as many nines as possible and decrease the sum by 9 respectively and when sum becomes less than

9 we print that digit and remaining digits should be zero.

if you have any doubt feel free to comment.

7 Likes
4

#include<conio.h>
#include<stdio.h>
int main()
{
int n;
int a[n],i,sum=0,m;
float avg;
printf(“enter array size”);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
sum=sum+a[i];
}
printf(" sum is %d",sum);

}
5

Here ya go @rashedcs My CODE.
I realized that that basic crux of solving this question is essentially the same as mentioned above.
As I see you have already solved it, good going mate ! :smiley:

6

is it possible to get pseudo code /code of your algorithm?

1 Like
7

Sure,
for finding out the max number start iterating from 0 to m-1 assigning 9 to every place and sum%9 when sum left with you is less than 9

However the trick comes in finding the minimal as they have put a restriction that there should be no leading zeroes thus we can’t just start assigning 9 to low priority digits(digits on the right), to escape that we assign a minimal of all digits i.e. 1 at the 0th index and start distributing max digit i.e. 9 from the (m-1)index all the way to 0, with remaining sum added to 0th index.

I hope this should work, if not I’ll rather provide code :slight_smile:

1 Like
8

please give the code.

9

Okay ! Started working on it

10

bro, can you please elaborate this?