13. Largest number possible

The problem can be found at the following link: Question Link

My Approach

To find the largest number possible with N digits and a given sum S, I followed these steps:

• Check if it's impossible to create a number with the given N and S.

  • If S is zero and N is greater than 1 or if the maximum possible sum of N single-digit numbers (9*N) is less than S, return "-1" because it's impossible.

• Initialize an empty string out to store the result.

• Loop N times to construct the number:

  • If S is greater than or equal to 9, add '9' to the out string and subtract 9 from S.

  • Otherwise, if S is not zero, add the remaining value of S as a string to the out string and set S to 0.

  • If S is zero, add '0' to the out string to fill the remaining digits.

• Return the out string as the largest number possible.

Time and Auxiliary Space Complexity

• Time Complexity: The algorithm runs in O(N) time because we iterate through the digits once.

• Auxiliary Space Complexity: The space complexity is O(N) because we store the result in the out string, which can have a maximum of N digits.

Code (C++)

class Solution {
public:
    string findLargest(int N, int S) {
        if ((!S && N > 1) || N * 9 < S) {
            return "-1";
        }
        string out;
        for (int i = 0; i < N; ++i) {
            if (S >= 9) {
                out += '9';
                S -= 9;
            } else {
                if (S) {
                    out += to_string(S);
                    S = 0;
                } else {
                    out += '0';
                }
            }
        }
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.