Digit Count in Range - Practice Coding Problems

Digit Count in Range - Problem

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].

For example, if d = 1, low = 1, and high = 13, then we need to count how many times the digit 1 appears in numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. The digit 1 appears in: 1 (once), 10 (once), 11 (twice), 12 (once), 13 (once), for a total of 6 occurrences.

Note: Each digit position in a multi-digit number is counted separately. For instance, the number 11 contains the digit 1 twice.

Input & Output

Example 1 — Basic Case

$ Input: d = 1, low = 1, high = 13

› Output: 6

💡 Note: Count digit 1 in range [1,13]: appears in 1 (1 time), 10 (1 time), 11 (2 times), 12 (1 time), 13 (1 time). Total = 6.

Example 2 — Digit Zero

$ Input: d = 0, low = 10, high = 20

› Output: 2

💡 Note: Count digit 0 in range [10,20]: appears in 10 (1 time), 20 (1 time). Total = 2.

Example 3 — Single Number

$ Input: d = 3, low = 3, high = 3

› Output: 1

💡 Note: Only number 3 in range, digit 3 appears once.

Constraints

0 ≤ d ≤ 9
1 ≤ low ≤ high ≤ 2 × 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Digit d=1, range [1,13]

Process

Count digit 1 in each number

Output

Total count = 6

Key Takeaway

🎯 Key Insight: Use mathematical digit DP to avoid iterating through every number in the range

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use mathematical digit DP to count digit occurrences by position rather than checking each number. The optimal approach analyzes each digit position (units, tens, hundreds) and calculates contributions mathematically. Time: O(log n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Iterate Through Range	O(n × k)	O(k)	Check each number in the range and count digit occurrences
Mathematical Digit DP	O(log n)	O(log n)	Use digit dynamic programming to count occurrences mathematically

Brute Force - Iterate Through Range — Algorithm Steps

Step 1: Loop through each number from low to high
Step 2: Convert number to string and count occurrences of digit d
Step 3: Add count to total result

Visualization

Tap to expand

Step-by-Step Walkthrough

Range

Numbers 1 through 13

Check

Count digit 1 in each number

Sum

Total count is 6

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(int d, int low, int high) {
    int count = 0;
    char digitChar = '0' + d;
    
    for (int num = low; num <= high; num++) {
        char numStr[20];
        sprintf(numStr, "%d", num);
        
        for (int i = 0; numStr[i]; i++) {
            if (numStr[i] == digitChar) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    int d, low, high;
    scanf("%d", &d);
    scanf("%d", &low);
    scanf("%d", &high);
    
    int result = solution(d, low, high);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

n numbers in range, k average digits per number for string processing

✓ Linear Growth

Space Complexity

O(k)

k space for string representation of each number

✓ Linear Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Iterate Through Range — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler