Leetcode 1067. Digit Count in Range

Problem Explanation:

The goal of the problem is to determine how many times a digit (d) occurs between a lower (low) and upper (high) bound. The bounds are inclusive, meaning that they are also checked for occurrences of the digit. This number can occur multiple times in a single integer (an example of this is the digit 1 occurring twice in the integer 11).

The approach we take to solve this problem is to count the number of times the digit appears in the range from 0 to high, then subtract how many times it appears in the range 0 to low - 1. This will give us the count of the digit in the range low to high.

The function countDigit is where most of the work is done. In this function, we iterate through the powers of 10 that are less than or equal to n (n is either low - 1 or high in this case). For each power of 10, we calculate the quotient and remainder of n divided by 10 times the current power of 10. The quotient tells us how many times the digit appears in the units of the current power of 10, and if it's greater than 0, we increment count by quotient * pow10.

Since we don't want to count leading zeroes, we decrement count by pow10 whenever d is 0.

Then we check if the remainder is greater than or equal to d times the current power of 10. If it is, that means the digit appears in the units of the current power of 10 in the remainder. We increment count by the smaller of (remainder - d * pow10 + 1) and pow10.

Let's take an example for better understanding:

Suppose d = 1, low = 1, and high = 13. To find the number of times 1 occurs in the numbers between 1 and 13, we find the number of times 1 occurs in the numbers between 0 and 13, then subtract from that the number of times 1 occurs in the numbers between 0 and 0. The former is easy - we get 6 when we count the 1's in the numbers [1,10,11,12,13]. The latter is also simple since 0 has no digits. Therefore, the answer is 6 - 0 = 6.

And now let's see the solutions for various programming languages:

Python

1
2 python
3class Solution:
4    def digitsCount(self, d: int, low: int, high: int) -> int:
5        def countDigit(n: int, d: int) -> int:
6            count = 0
7            pow10 = 1
8            while pow10 <= n:
9                divisor = pow10 * 10
10                quotient = n // divisor
11                remainder = n % divisor
12                if quotient > 0:
13                    count += quotient * pow10
14                if d == 0:
15                    count -= pow10
16                if remainder >= d * pow10:
17                    count += min(remainder - d * pow10 + 1, pow10)
18                pow10 *= 10
19            return count
20
21        return countDigit(high, d) - countDigit(low - 1, d)

Java

1
2 java
3public class Solution {
4    public int digitsCount(int d, int low, int high) {
5        return countDigit(high, d) - countDigit(low - 1, d);
6    }
7
8    private int countDigit(int n, int d) {
9        int count = 0;
10
11        for (int pow10 = 1; pow10 <= n; pow10 *= 10) {
12            int divisor = pow10 * 10;
13            int quotient = n / divisor;
14            int remainder = n % divisor;
15            if (quotient > 0)
16                count += quotient * pow10;
17            if (d == 0)
18                count -= pow10;
19            if (remainder >= d * pow10)
20                count += Math.min(remainder - d * pow10 + 1, pow10);
21        }
22
23        return count;
24    }
25}

JavaScript

1
2 javascript
3class Solution {
4    digitsCount(d, low, high) {
5        return this.countDigit(high, d) - this.countDigit(low - 1, d);
6    }
7
8    countDigit(n, d) {
9        let count = 0;
10
11        for (let pow10 = 1; pow10 <= n; pow10 *= 10) {
12            let divisor = pow10 * 10;
13            let quotient = Math.floor(n / divisor);
14            let remainder = n % divisor;
15            if (quotient > 0)
16                count += quotient * pow10;
17            if (d == 0)
18                count -= pow10;
19            if (remainder >= d * pow10)
20                count += Math.min(remainder - d * pow10 + 1, pow10);
21        }
22
23        return count;
24    }
25}

C++

1
2 c++
3class Solution {
4public:
5    int digitsCount(int d, int low, int high) {
6        return countDigit(high, d) - countDigit(low - 1, d);
7    }
8
9private:
10    int countDigit(int n, int d) {
11        int count = 0;
12
13        for (int pow10 = 1; pow10 <= n; pow10 *= 10) {
14            int divisor = pow10 * 10;
15            int quotient = n / divisor;
16            int remainder = n % divisor;
17            if (quotient > 0)
18                count += quotient * pow10;
19            if (d == 0)
20                count -= pow10;
21            if (remainder >= d * pow10)
22                count += std::min(remainder - d * pow10 + 1, pow10);
23        }
24
25        return count;
26    }
27};

C#

1
2 C#
3public class Solution {
4    public int DigitsCount(int d, int low, int high) {
5        return CountDigit(high, d) - CountDigit(low - 1, d);
6    }
7
8    private int CountDigit(int n, int d) {
9        int count = 0;
10
11        for (int pow10 = 1; pow10 <= n; pow10 *= 10) {
12            int divisor = pow10 * 10;
13            int quotient = n / divisor;
14            int remainder = n % divisor;
15            if (quotient > 0)
16                count += quotient * pow10;
17            if (d == 0)
18                count -= pow10;
19            if (remainder >= d * pow10)
20                count += Math.Min(remainder - d * pow10 + 1, pow10);
21        }
22
23        return count;
24    }
25}

Kotlin

1
2kotlin
3class Solution {
4    fun digitsCount(d: Int, low: Int, high: Int): Int {
5        return countDigit(high, d) - countDigit(low - 1, d)
6    }
7
8    private fun countDigit(n: Int, d: Int): Int {
9        var count = 0
10        var pow10 = 1
11        while (pow10 <= n) {
12            val divisor = pow10 * 10
13            val quotient = n / divisor
14            val remainder = n % divisor
15            if (quotient > 0) {
16                count += quotient * pow10
17            }
18            if (d == 0) {
19                count -= pow10
20            }
21            if (remainder >= d * pow10) {
22                count += kotlin.math.min(remainder - d * pow10 + 1, pow10)
23            }
24            pow10 *= 10
25        }
26        return count
27    }
28}

Swift

1
2swift
3class Solution {
4    func digitsCount(_ d: Int, _ low: Int, _ high: Int) -> Int {
5        return countDigit(high, d) - countDigit(low - 1, d)
6    }
7
8    private func countDigit(_ n: Int, _ d: Int) -> Int {
9        var count = 0
10        var pow10 = 1
11        while pow10 <= n {
12            let divisor = pow10 * 10
13            let quotient = n / divisor
14            let remainder = n % divisor
15            if quotient > 0 {
16                count += quotient * pow10
17            }
18            if d == 0 {
19                count -= pow10
20            }
21            if remainder >= d * pow10 {
22                count += min(remainder - d * pow10 + 1, pow10)
23            }
24            pow10 *= 10
25        }
26        return count
27    }
28}

Go

1
2go
3type Solution struct {}
4
5func (s Solution) digitsCount(d int, low int, high int) int {
6    return s.countDigit(high, d) - s.countDigit(low - 1, d)
7}
8
9func (s Solution) countDigit(n int, d int) int {
10    count := 0
11    pow10 := 1
12    for pow10 <= n {
13        divisor := pow10 * 10
14        quotient := n / divisor
15        remainder := n % divisor
16        if quotient > 0 {
17            count += quotient * pow10
18        }
19        if d == 0 {
20            count -= pow10
21        }
22        if remainder >= d * pow10 {
23            count += min(remainder - d * pow10 + 1, pow10)
24        }
25        pow10 *= 10
26    }
27    return count
28}
29
30func min(x, y int) int {
31    if x < y {
32        return x
33    }
34    return y
35}

Each of the above functions for various programming languages implements the same logic as explained above to find the number of occurrences of a given integer in a given range. The code varies slightly based on the distinct syntax and peculiarities of each programming language. Nonetheless, the underlying approach and logic remain the same.