Welcome to Subscribe On Youtube

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)$.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions