4000 LeetCode problem solution

Previously, I described the first problems from 4000 to 4010, except for 4004 and 4005.

Below is the solution to LeetCode problem 4000.

LeetCode link: 4000. Largest Integer With Given Digit Sum

4000 LeetCode problem: 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

LeetCode 4000 problem: solution explanation

This is problem of the easy level. The hardest part is figuring out how to obtain the largest possible number. For this we can use simple math:

To get the largest possible number, we need to place the largest possible digits as far to the left as possible.

Therefore, if a number has at most n digits, the maximum possible digit sum is achieved when all n digits are 9s. Hense:

maximum digit sum = 9 * n

First, we need to check whether it is possible to achieve the sum s at all. So, if:

s > 9 * n

we return -1.

Time complexity: O(n)
Space complexity: O(1)

LeetCode 4000 C++ solution

class Solution {
public:
  int largestInteger(int n, int s) {
    if(s > 9 * n) return -1;

    int result = 0;

    for(int i = 0; i < n; i++)
    {
      int digit = min(9, s);

      result = result * 10 + digit;
      s -= digit;
    }

    return result;
  }
};

LeetCode 4000 Java solution

class Solution {
  public int largestInteger(int n, int s) {
    if(s > 9 * n) return -1;

    int result = 0;

    for(int i = 0; i < n; i++) {
      int digit = Math.min(9, s);

      result = result * 10 + digit;
      s -= digit;
    }

    return result;
  }
}

LeetCode 4000 JavaScript solution

var largestInteger = function(n, s) {
  if(s > 9 * n) return -1;

  let result = 0;

  for(let i = 0; i < n; i++) {
    const digit = Math.min(9, s);

    result = result * 10 + digit;
    s -= digit;
  }

  return result;
};

LeetCode 4000 TypeScript solution

function largestInteger(n: number, s: number): number {
  if(s > 9 * n) return -1;

  let result = 0;

  for(let i = 0; i < n; i++) {
    const digit = Math.min(9, s);

    result = result * 10 + digit;
    s -= digit;
  }

  return result;
};

LeetCode 4000 Python solution

class Solution:
  def largestInteger(self, n: int, s: int) -> int:
    if s > 9 * n: return -1

    result = 0

    for _ in range(n):
      digit = min(9, s)

      result = result * 10 + digit
      s -= digit

    return result