Skip to main content
Talentd

Digit Count in Range - Solution & Explanation

HardPremiumFree on FleetCodeMathDynamic Programming6 min readAsked at: Amazon
Practice this problem

Problem Statement

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

 

Example 1:

Input: d = 1, low = 1, high = 13
Output: 6
Explanation: The digit d = 1 occurs 6 times in 1, 10, 11, 12, 13.
Note that the digit d = 1 occurs twice in the number 11.

Example 2:

Input: d = 3, low = 100, high = 250
Output: 35
Explanation: The digit d = 3 occurs 35 times in 103,113,123,130,131,...,238,239,243.

 

Constraints:

  • 0 <= d <= 9
  • 1 <= low <= high <= 2 * 108

Approach Overview

Problem Overview: You are given a digit d and a range [low, high]. The task is to count how many times digit d appears in every number within that inclusive range. The challenge is handling large ranges efficiently without iterating through each number.

Approach 1: Brute Force Digit Counting (O(n log n) time, O(1) space)

The most direct approach iterates through every integer from low to high. For each number, repeatedly extract digits using num % 10 and num // 10, and increment a counter whenever the extracted digit equals d. Since each number has up to log10(n) digits, the total work becomes O((high - low) * log n). This works for small ranges but quickly becomes too slow when the interval spans millions or billions of numbers.

Approach 2: Digit DP / Positional Counting (O(log n) time, O(log n) space)

The optimal solution counts occurrences of digit d from 0 to a number x, then computes the final result as count(high) - count(low - 1). Instead of checking each number individually, analyze each digit position (units, tens, hundreds, etc.). For a given position, determine how many full cycles of digits appear and how many extra digits contribute to the count. This approach relies on positional math and a form of digit dynamic programming where the prefix of the number constrains valid digit choices.

At each digit position, track three components: digits to the left of the current position, the digit at the current position, and digits to the right. These determine how many times digit d appears in that position across all numbers ≤ x. Special handling is required when d = 0 because leading zeros are not valid digits in the representation of a number.

This technique reduces the complexity to the number of digits in high, which is typically at most 10 for 32-bit integers. The algorithm runs in O(log n) time and uses O(log n) auxiliary space if implemented with digit arrays or recursion. The logic is rooted in math and dynamic programming patterns commonly seen in digit DP problems.

Recommended for interviews: Interviewers expect the positional counting or digit DP approach. Starting with the brute force solution demonstrates understanding of the problem, but the optimized count(high) - count(low - 1) strategy shows you recognize the mathematical structure of digit ranges and can design an O(log n) algorithm.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Digit CountingO(n log n)O(1)Useful for small ranges or verifying correctness during development
Digit DP / Positional CountingO(log n)O(log n)Optimal solution for large ranges where iterating through numbers is infeasible

Video Solution

【每日一题】LeetCode 1067. Digit Count in Range • Huifeng Guan • 530 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Digit Count in Range easy or hard?
Digit Count in Range is considered a Hard problem because it requires understanding digit DP or positional digit counting. The brute force idea is simple, but designing the O(log n) mathematical solution requires deeper insight into number patterns.
Digit Count in Range Python/Java solution
Implement a helper function that counts occurrences of digit d from 0 to x using positional math. Call it for high and low-1, then subtract. The same logic works across Python, Java, C++, and Go since it only involves arithmetic operations and loops.
How to solve Digit Count in Range in O(log n)?
Compute a helper function count(x, d) that counts occurrences of digit d in numbers from 0 to x. Iterate through each digit position (units, tens, hundreds) and calculate contributions using the digits to the left and right. The final answer is count(high, d) minus count(low - 1, d).
What is the best approach for Digit Count in Range?
The most efficient approach uses digit DP or positional digit counting. Instead of iterating through every number, compute how many times digit d appears from 0 to high and subtract the count from 0 to low-1. This reduces the complexity to O(log n), proportional to the number of digits.
Is Digit Count in Range asked at Google/Amazon/Meta?
Digit counting and digit DP problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test mathematical reasoning, number decomposition, and dynamic programming patterns over digit positions.
What data structure is used in Digit Count in Range?
The solution mainly relies on mathematical digit decomposition and sometimes a small DP table or digit array. No heavy data structures are required; the algorithm operates on digits of the number and positional calculations.
What is the time complexity of Digit Count in Range?
The optimal digit DP or positional counting solution runs in O(log n) time because it processes each digit position of the number once. Brute force solutions require O((high - low) * log n) time since each number and its digits must be examined.

Ready to solve this problem?

Practice Digit Count in Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Digit One

Next

Sum of Numbers With Units Digit K