Scale Engineer

Count of Integers

Hard
#2453Time: O((num2 - num1) * L), where L is the average number of digits in the numbers in the range. Given that `num2` can be up to 10^22, this is far too slow.Space: O(L), where L is the number of digits in `num2`. This space is required to store the `BigInteger` representation of the current number.2 companies
Patterns
MathDynamic Programming
Data structures
String
Companies
CiscoMorgan Stanley

Prompt

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:

min_sum

Example 2:

min_sum

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process directly. We can iterate through every integer x from num1 to num2, calculate the sum of its digits, and check if this sum falls within the given [min_sum, max_sum] range. If it does, we increment a counter. Due to the massive size of num1 and num2 (up to 10^22), we must use a data type that can handle arbitrarily large integers, such as BigInteger in Java.

Algorithm

  1. Initialize a counter count to 0.
  2. Use BigInteger to handle the large numbers num1 and num2.
  3. Create a loop that iterates from num1 to num2, incrementing by one in each step.
  4. For each number in the loop: a. Convert the BigInteger to a string. b. Calculate the sum of its digits by iterating through the string characters. c. Check if the calculated digit sum lies within the range [min_sum, max_sum]. d. If the condition is true, increment the count.
  5. After the loop finishes, return the final count.

Walkthrough

This method involves a simple loop from the starting number num1 to the ending number num2. For each number, we perform a check. The check consists of two parts: calculating the digit sum and comparing it with min_sum and max_sum. While simple to conceptualize, the number of iterations can be enormous, making this approach computationally infeasible for the constraints of the problem.

import java.math.BigInteger; // This is a conceptual example that will time out.class Solution {    public int count(String num1, String num2, int min_sum, int max_sum) {        BigInteger current = new BigInteger(num1);        BigInteger end = new BigInteger(num2);        long count = 0;        int MOD = 1_000_000_007;         while (current.compareTo(end) <= 0) {            if (isGood(current, min_sum, max_sum)) {                count++;            }            current = current.add(BigInteger.ONE);        }        // The count can be large, but the problem asks for the final result modulo 10^9+7.        // However, since we can't even finish the loop, this is a moot point.        return (int)(count % MOD);    }     private boolean isGood(BigInteger n, int min_sum, int max_sum) {        String s = n.toString();        int sum = 0;        for (char c : s.toCharArray()) {            sum += c - '0';            if (sum > max_sum) { // Small optimization                return false;            }        }        return sum >= min_sum && sum <= max_sum;    }}

Complexity

Time

O((num2 - num1) * L), where L is the average number of digits in the numbers in the range. Given that `num2` can be up to 10^22, this is far too slow.

Space

O(L), where L is the number of digits in `num2`. This space is required to store the `BigInteger` representation of the current number.

Trade-offs

Pros

  • Easy to understand and implement.

  • Correct for small ranges of num1 and num2.

Cons

  • Extremely inefficient and will cause a 'Time Limit Exceeded' error on any platform for the given constraints.

  • The difference between num2 and num1 can be very large (up to 10^22), making iteration impossible.

Solutions

import java.math.BigInteger ; class Solution { private final int mod = ( int ) 1 e9 + 7 ; private Integer [][] f ; private String num ; private int min ; private int max ; public int count ( String num1 , String num2 , int min_sum , int max_sum ) { min = min_sum ; max = max_sum ; num = num2 ; f = new Integer [ 23 ][ 220 ]; int a = dfs ( 0 , 0 , true ); num = new BigInteger ( num1 ). subtract ( BigInteger . ONE ). toString (); f = new Integer [ 23 ][ 220 ]; int b = dfs ( 0 , 0 , true ); return ( a - b + mod ) % mod ; } private int dfs ( int pos , int s , boolean limit ) { if ( pos >= num . length ()) { return s >= min && s <= max ? 1 : 0 ; } if (! limit && f [ pos ][ s ] != null ) { return f [ pos ][ s ]; } int ans = 0 ; int up = limit ? num . charAt ( pos ) - '0' : 9 ; for ( int i = 0 ; i <= up ; ++ i ) { ans = ( ans + dfs ( pos + 1 , s + i , limit && i == up )) % mod ; } if (! limit ) { f [ pos ][ s ] = ans ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem