1. Introduction
Counting the occurrences of a digit in a range of integers is a common programming problem. The goal is to determine how many times a given digit appears in a range of integers, which can be helpful for various applications, such as data analysis or password cracking.
In this tutorial, we’ll discuss how to count the occurrences of a digit in a range of integers. We’ll highlight two important approaches – a loop-based approach and an optimized approach that minimizes the space and time complexity.
2. Explanation of the Problem
Suppose we are working as census takers and our task is to assign a unique 3-digit number tag to each house in a specific geographic area. Our first task is to determine how many of each digit (0-9) we need to order from a silver tag producer to ensure that we have enough tags for all the houses in the area.
To accomplish this, we would need to count the number of houses in the area to determine the upper limit of the number tag range. Let’s assume that we have already numbered 500 houses in the area and we are moving to a new community with 1000 houses.
This means that the upper limit of our new number range will be 1500, with the lower limit being 501 (since we have already numbered the first 500 houses).
Next, we would need to determine how many times each digit (0-9) appears in the new number range from 501 to 1500. Other examples include counting the occurrence of each digit (0-9) between:
- 1 to 1000
- 20 to 100
- 0 to 10000
There are various approaches to counting the occurrences of a digit in a range of integers. A common approach is a loop-based method. While this approach is simple to implement, it can be computationally expensive and time-consuming for larger number ranges, especially when compared to more efficient algorithms.
3. The Loop-Based Approach
The algorithm for counting occurrences of a digit in a given range of integers using the loop-based approach:
algorithm countDigit(start_range, end_range, digit):
// INPUT
// start = the starting number of the range
// end = the ending number of the range
// digit = the digit to count the occurrences of
// OUTPUT
// The number of times the digit occurs in the range of numbers from start to end.
count <- 0
for i <- start to end:
num <- str(i)
for j <- 1 to length(num):
if num[j] = str(digit):
count <- count + 1
return count
This approach involves iterating through each integer in the given range and converting each integer to a string. The code then iterates through each character in the string and checks if it matches the desired digit. If a match is found, the counter is incremented.
4. The Optimized Approach
Here, counting the occurrences of a digit is achieved by iterating through each number in the range and using integer division to remove the last digit of the number and check if it’s equal to the target digit, thereby avoiding the need to convert each number to a string and iterate through each digit using a nested loop:
algorithm countDigit(start, end, digit):
// INPUT
// start = the starting number of the range
// end = the ending number of the range
// digit = the digit to count the occurrences of
// OUTPUT
// The number of times digit occurs in the range of numbers from start to end.
count <- 0
for num <- start to end:
while num > 0:
if num mod 10 = digit:
count <- count + 1
num <- divide num by 10 and drop the remainder
return count
This approach uses a 
loop to iterate through each number in the range from 
to 
. For each number 
, the loop uses integer division by 10 to remove the last digit of the number and check if it’s equal to the target digit.
This allows the function to count the number of occurrences of the target digit in each number without having to convert each number to a string and iterate through each digit using a nested loop.
By using integer division in the loop instead of converting each number to a string, the function reduces its time complexity from 
to 
where 
is the maximum number of digits in any number in the range, and 
is the number of numbers in the range.
The space complexity of the function is also reduced from to 
, as it does not use any additional data structures to store the input or output.
5. Conclusion
In this article, we discussed two approaches to how to count the occurrences of a digit in a range of integers. The first approach is a brute force approach that iterates through the range of numbers and every digit in each number. Whereas the second approach optimizes the brute force approach by introducing an integer division.