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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.