Skip to content

4000. Largest Integer With Given Digit Sum

Description

You are given two non-negative integers n and s.

Return the largest integer that has at most n digits and whose sum of digits is s. If no such integer exists, return -1.

Β 

Example 1:

Input: n = 2, s = 9

Output: 90

Explanation:

The largest integer with at most 2 digits that has a sum of digits of 9 is 90.

Example 2:

Input: n = 2, s = 19

Output: -1

Explanation:

There is no integer with at most 2 digits that has a sum of digits of 19, so the answer is -1.

Example 3:

Input: n = 5, s = 0

Output: 0

Explanation:

The only non-negative integer whose digits sum to 0 is 0.

Β 

Constraints:

  • 1 <= n <= 5
  • 0 <= s <= 100

Solutions

Solution 1: Greedy

If \(n \times 9 < s\), even filling every digit with \(9\) cannot reach digit sum \(s\), so return \(-1\).

Otherwise, to maximize the integer, assign as large a digit as possible to higher places. Construct \(n\) digits from high to low: each digit takes \(\min(s, 9)\), then subtract that value from \(s\). The resulting integer is the answer (if \(s = 0\), the result is \(0\)).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def largestInteger(self, n: int, s: int) -> int:
        if n * 9 < s:
            return -1
        ans = 0
        for _ in range(n):
            x = min(s, 9)
            ans = ans * 10 + x
            s -= x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int largestInteger(int n, int s) {
        if (n * 9 < s) {
            return -1;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = Math.min(s, 9);
            ans = ans * 10 + x;
            s -= x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int largestInteger(int n, int s) {
        if (n * 9 < s) {
            return -1;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = min(s, 9);
            ans = ans * 10 + x;
            s -= x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func largestInteger(n int, s int) (ans int) {
    if n*9 < s {
        return -1
    }
    for i := 0; i < n; i++ {
        x := min(s, 9)
        ans = ans*10 + x
        s -= x
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function largestInteger(n: number, s: number): number {
    if (n * 9 < s) {
        return -1;
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        const x = Math.min(s, 9);
        ans = ans * 10 + x;
        s -= x;
    }
    return ans;
}

Comments