Coding

Digit Count in Range

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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

Input: d = 2, low = 2, high = 25 Output: 9 Explanation: The digit d = 2 occurs 9 times in 2,20,12,21, 22, 23, 24,25.

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.

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

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

cpp

class Solution {
    public:
    int digitsCount(int d, int low, int high) {
        //User code goes here
        
    }
};

java

class Solution {
    public int digitsCount(int d, int low, int high) {
        // User code goes here
    }
}

python

class Solution:
    def digitsCount(self, d: int, low: int, high: int) -> int:
        # User code goes here

javascript

class Solution {
    digitsCount(d, low, high) {
        // User Code goes here
    }
}

csharp

public class Solution
{
    public int DigitsCount(int d, int low, int high)
    {
        // User code goes here
    }
}

func digitsCount(d int, low int, high int) int {
	// User code goes here
}

Stuck? Show a way to structure it+

01Compute occurrences in `[1,n]` and subtract `count(low-1)`.
02For each decimal factor, split n into higher, current, and lower parts.
03Use the standard three-case formula for nonzero digit d.
04Handle d=0 separately to avoid counting leading zeroes.

Reference answer

Define count(n,d) for the inclusive range 1..n, then answer count(high,d)-count(low-1,d). At each decimal factor f=1,10,..., compute higher=n/(f*10), cur=(n/f)%10, and lower=n%f. For d>0, the contribution is higher*f, plus f if cur>d, plus lower+1 if cur==d. Zero cannot use that formula because leading positions are not written: reduce the higher-group count by one and only add a partial contribution when a real higher prefix exists. Iterate O(log10 n) positions using 64-bit arithmetic. Test boundaries such as 9, 10, 99, and ranges containing zero if the domain permits it.

Then expect these follow-ups

How would you count all digits 0 through 9 at once?
Tests: digit counting
How would a digit-DP solution handle arbitrary bounds?
Tests: digit DP

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question