2719. Count of Integers

Description

You are given two numeric strings num1 and num2 and two integers max_sum and min_sum. We denote an integer x to be good if:

• num1 <= x <= num2
• min_sum <= digit_sum(x) <= max_sum.

Return the number of good integers. Since the answer may be large, return it modulo 109 + 7.

Note that digit_sum(x) denotes the sum of the digits of x.

 

Example 1:

Input: num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output: 11
Explanation: There are 11 integers whose sum of digits lies between 1 and 8 are 1,2,3,4,5,6,7,8,10,11, and 12. Thus, we return 11.

Example 2:

Input: num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output: 5
Explanation: The 5 integers whose sum of digits lies between 1 and 5 are 1,2,3,4, and 5. Thus, we return 5.

 

Constraints:

• 1 <= num1 <= num2 <= 1022
• 1 <= min_sum <= max_sum <= 400

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n*max_sum*2²*10)
• Space complexity: O(n*max_sum*2²)

 

JavaScript

/**
 * @param {string} num1
 * @param {string} num2
 * @param {number} min_sum
 * @param {number} max_sum
 * @return {number}
 */
const MODULO = 10 ** 9 + 7;

const count = function (num1, num2, min_sum, max_sum) {
  const n = num2.length;
  const num1Padded = num1.padStart(n, '0');
  const maxCount = solveForSum(num1Padded, num2, n, max_sum);
  const minCount = solveForSum(num1Padded, num2, n, min_sum - 1);

  return (maxCount - minCount + MODULO) % MODULO;
};

function getCountRecursive(index, sum, minTight, maxTight, config) {
  if (sum < 0) return 0;
  if (index === config.n) return 1;

  const t1 = minTight ? 1 : 0;
  const t2 = maxTight ? 1 : 0;
  const key = ((index * (config.maxSum + 1) + sum) * 2 + t1) * 2 + t2;

  if (config.dp[key] !== -1) return config.dp[key];

  const minNum = minTight ? Number(config.num1[index]) : 0;
  const maxNum = maxTight ? Number(config.num2[index]) : 9;
  let result = 0;

  for (let d = minNum; d <= maxNum; d++) {
    const nextMinTight = minTight && d === minNum;
    const nextMaxTight = maxTight && d === maxNum;

    const count = getCountRecursive(index + 1, sum - d, nextMinTight, nextMaxTight, config);
    result = (result + count) % MODULO;
  }

  config.dp[key] = result;

  return result;
}

function solveForSum(num1, num2, n, maxSum) {
  if (maxSum < 0) return 0;

  const dpSize = n * (maxSum + 1) * 2 * 2;
  const config = {
    num1,
    num2,
    n,
    maxSum,
    dp: new Int32Array(dpSize).fill(-1),
  };

  return getCountRecursive(0, maxSum, true, true, config);
}