Find the largest number with given number of digits and sum of digits

Reading time: 30 minutes | Coding time: 5 minutes

In this problem, we need to find the largest number with a given number of digits N and given sum of digits say M. We will use a greedy algorithm to solve this is O(N) time complexity.

Example:

If N (number of digits) = 3 and M (sum of digits) = 15

Then, the largest number satisfying it will be 960.
There are other numbers as well but they are smaller than 960 like 186, 159, 357 and more.

Let us take another example to understand this. N = 2 and M = 11.
Then, the largest number satisfying it is 92 while other numbers are 38, 29, 56 and more.

Let us make some observations to arrive at our solution.

If a number has 3 digits like:

d0 d1 d2 

where d0 is the most significant digit and d2 is the least significant digit.

The maximum value that can be assigned to d0, d1 and d2 are 9 and hence, the maximum number can be 999.

So, our first focus should be to make all digits 9.

Note, that if there are N digits and we make our digits 9, then the sum becomes 9 * N. The given sum may be smaller so we cannot place 9 for all digits.

If we have a chose between 9 and 5, we should place 9 at the most significant digit and 5 at the least significant digit.

In this line, we make our second observation that is:

Most significant digit should have higher digit value compared to less significant digits.

The algorithm is to substract 9 from the original number as long as the number is greater than 9 and then, place the number (<9) in the current digit place and the remaining digit places become 0.

Steps:

• We are given N digits and M sum.
• We initialize an array of integer of size N. Index 0 is least significant and N-1 is most significant.

[0 0 ... 0 0]

• current index = N-1
• If N >= 9 then place 9 at index N-1, decrement current index by 1 and modify N as N-9. Now repeat this step.
• If N < 9, then place N at the current index and exit.

Instead of using an array, we can use a number directly as it will be memory efficient. The time complexity will be same.

Steps for memory efficient version:

• We are given N digits and M sum.
• We initialize an integer answer as 0.
• current index = N-1
• If N >= 9 then multiply answer by 10 and then add 9 and modify N as N-9. Decrement current index by 1. Now repeat this step.

answer = answer * 10 + 9;
N = N -9;

• If N < 9, then multiple answer by 1o and then add N. Following it, multiply answer by 10 current index - 1 times.

answer = answer * 10 + N;
while(current index > 0)
    answer = answer * 10;

Pseudocode

Following is the pseudocode:

int largest_number(int digits, int sum)
{
    int current_index = digit; 
    int answer = 0;
    while(sum > 0)
    {
        if(sum >= 9)
            answer = answer * 10 + 9;
        else
            answer = answer * 10 + N;
        sum = sum - 9;
        --current_index;
     }
     while(current_index > 0)
     {
         answer = answer * 10;
         --current_index;
     }
}

Let us follow our algorithm along an example:

N = 5 (digits), M = 23 (sum)

Let answer be 0 initially

As 23 >= 9, answer = 0 * 10 + 9 = 9 and N = 5-1 = 4 and M = 23 - 9 = 14

As 14 >= 9, answer = 9 * 10 + 9 = 99 and N = 4-1 = 3 and M = 14 - 9 = 5

As 5 < 9, answer = 99 * 10 + 5 = 995 and N = 3-1 = 2 and M = 5 - 5 = 0

As M = 0, answer = 995 * 10 * 10 (multiply by 10 2 (N) times) = 99500

Hence, our answer is 99500.

Implementation

Following is the implementation in Java:

class opengenus 
{
    static long largest_number(int digits, int sum)
    {
        int current_index = digits; 
        long answer = 0;
        while(sum > 0)
        {
            if(sum >= 9)
            {
                answer = answer * 10 + 9;
                sum = sum - 9;
            }
            else
            {
                answer = answer * 10 + sum;
                sum = 0;
            }
            --current_index;
         }
         while(current_index > 0)
         {
             answer = answer * 10;
             --current_index;
         }
         return answer;
    }
	public static void main (String[] args) 
	{
		int N = 10, M = 60;
		long answer = largest_number(N, M);
		System.out.println(answer);
	}
}

Note that above method will fail if the value of the answer is greater than the value that can be stored in an integer. For this, you may use:

• array method as we demonstrated
• use a string instead of integer
• use a bigger data type like BigInteger in Java

With this, you have the complete knowledge of solving this problem. Enjoy.