Posts Largest number possible (geeksforgeeks - SDE Sheet)
Post
Cancel

Largest number possible (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given two numbers ‘N’ and ‘S’ , find the largest number that can be formed with ‘N’ digits and whose sum of digits should be equals to ‘S’. Return -1 if it is not possible.

geeksforgeeks

SOLUTION

Edge Cases:

  • If the sum is 0 and N > 1, it is impossible to form such a number, as the only valid number would be 0, which can only be represented as a single digit.
  • If the sum S exceeds the maximum possible sum with N digits, it is not possible to form such a number.

Main Steps:

  • Start with an empty result and iterate N times to construct the number.
  • For each digit:
    • If the remaining sum is greater than or equal to 9, append 9 to the result. Reduce the target sum by 9.
    • If the remaining sum is less than 9, append the remaining sum itself and set the sum to 0, ensuring that subsequent digits are zeros, as no further changes to the sum are needed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution{

    static String findLargest(int N, int S){

        StringBuffer sb = new StringBuffer();

        // edge case:
        // if the total sum needed is 0, and we need to use more than 1 digit
        // return -1;
        if(S == 0 && N > 1)
            return "-1";

        // edge case:
        // if the maximum sum possible using N digits (by using all 9s) is still less than target sum
        // return -1;
        if(N * 9 < S)
            return "-1";

        // loop N times to form the N digit number
        for(int i=0; i<N; i++){

            // if the target value is more than 9, append 9 to the current number
            if(S >= 9){
                sb.append("9");
                // reduce target sum by 9
                S -= 9;

            // otherwise, append the remaining value in S which will be lower than 9
            // if there are more digits left, they need to be appended as 0, so we set the S value to 0
            }else{

                sb.append(String.valueOf(S));
                S = 0;

            }

        }

        return sb.toString();

    }

}
This post is licensed under CC BY 4.0 by the author.