We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Digit Count in Range

Number: 1068

Difficulty: Hard

Paid? Yes

Companies: Amazon

Problem Description

Given a single-digit integer d and two integers low and high, count the number of times that d occurs as a digit in every integer in the inclusive range [low, high].

Key Insights

  • A brute-force iteration over the range [low, high] is too slow given the constraint high ≤ 2×10^8.
  • We can use Digit Dynamic Programming (DP) to count occurrences of d in numbers up to a given limit.
  • Calculate the count for the interval [0, high] and subtract the count for [0, low-1] to get the final answer.
  • Care must be taken when d is 0, as leading zeroes should be handled correctly (they are not considered once the number starts).

Space and Time Complexity

Time Complexity: O(log(n) * (constant factor)) per DP call, where n is the high value. Space Complexity: O(log(n)) due to recursion depth and memoization storage.

Solution

We solve this problem using Digit DP. The approach is to build the count for every number from 0 up to n using recursion with memoization. At each digit position, we decide the current digit from 0 to a limit (which is the current digit of n if we are bounded by n’s prefix). The DP state considers:

  • The current position in the digit string.
  • Whether the prefix so far is "tight" (exactly matching the prefix of n).
  • Whether we have begun placing non-zero digits (to avoid counting leading zeros).

The DP returns a tuple containing:

  • The total number of times d occurs from the current state.
  • The total number of numbers possible from the current state.

After computing the count for 0 to high and for 0 to low-1, subtracting the two gives the desired result for the range [low, high].

Code Solutions

# Python solution using Digit DP
from functools import lru_cache

def count_digit_occurrences(n, d):
    # Convert n to a list of digits for easier processing in DP.
    digits = list(map(int, str(n)))
    length = len(digits)
    
    # dp(pos, tight, leading) returns (count, count_numbers)
    @lru_cache(maxsize=None)
    def dp(pos, tight, leading):
        if pos == length:
            return (0, 1)  # End state: no occurrences, one valid number.
        
        total_count = 0
        total_numbers = 0
        limit = digits[pos] if tight else 9
        
        for dig in range(0, limit+1):
            new_tight = tight and (dig == limit)
            new_leading = leading and (dig == 0)
            count_future, numbers_future = dp(pos+1, new_tight, new_leading)
            add = 0
            # If the number has started and the digit equals d, add the number of completions.
            if not new_leading and dig == d:
                add = numbers_future
            total_count += add + count_future
            total_numbers += numbers_future
        return (total_count, total_numbers)
    
    return dp(0, True, True)[0]

def digit_count_in_range(d, low, high):
    # Count occurrences from 0 to high and subtract count from 0 to (low - 1) 
    return count_digit_occurrences(high, d) - count_digit_occurrences(low - 1, d)

# Example usage:
if __name__ == "__main__":
    d = 1
    low = 1
    high = 13
    print(digit_count_in_range(d, low, high))  # Expected output: 6
← Back to All Questions