Skip to main content
Talentd

Count Digit Appearances - Solution & Explanation

MediumArrayMath6 min read
Practice this problem

Problem Statement

You are given an integer array nums and an integer digit.

Return the total number of times digit appears in the decimal representation of all elements in nums.

 

Example 1:

Input: nums = [12,54,32,22], digit = 2

Output: 4

Explanation:

The digit 2 appears once in 12 and 32, and twice in 22. Thus, the total number of times digit 2 appears is 4.

Example 2:

Input: nums = [1,34,7], digit = 9

Output: 0

Explanation:

The digit 9 does not appear in the decimal representation of any element in nums, so the total number of times digit 9 appears is 0.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 106​​​​​​​
  • 0 <= digit <= 9

Approach Overview

Problem Overview: You receive an integer n and a digit d. The goal is to count how many times digit d appears in the decimal representation of all numbers from 0 to n.

Approach 1: Brute Force Enumeration (O(n log n) time, O(1) space)

The most direct solution iterates through every number from 0 to n. Convert each number to a string or repeatedly extract digits using % 10 and / 10. For every digit encountered, compare it with d and increment the counter. Each number has at most log10(n) digits, which leads to O(n log n) total work. This approach is useful for understanding the problem but becomes slow when n grows large.

Approach 2: Positional Digit Counting (O(log n) time, O(1) space)

A faster method analyzes each digit position independently. For a position value factor = 1, 10, 100..., split the number into three parts: higher, current, and lower. These represent the digits left of the position, the digit at the position, and the digits to the right. Using these values, you can determine how many full cycles of the digit occur at that position and adjust based on the current digit. Iterate through all positions until factor > n. Since the number of positions is log10(n), the algorithm runs in O(log n) time with constant memory.

Approach 3: Digit Dynamic Programming (O(d * 10) time, O(d) space)

For generalized counting problems—especially when constraints include digit limits or multiple queries—digit DP provides a structured approach. Traverse the digits of n from most significant to least significant while tracking whether the current prefix is restricted by the upper bound. Maintain state for the position and the number of occurrences counted so far. Although heavier than the positional formula, it easily extends to variations such as counting digits under additional constraints.

Recommended for interviews: Start by explaining the brute force scan to show understanding of the digit counting process. Then transition to the positional math approach. Interviewers usually expect the O(log n) solution because it demonstrates number decomposition and efficient counting. If the problem expands with constraints or ranges, mentioning mathematical digit analysis or digit DP shows deeper problem‑solving range.

Solution

We traverse each element in the array and count how many times digit appears. For each element, we can obtain each of its digits by repeatedly taking the modulo and dividing by 10, and compare each digit with digit. If they are equal, we increment the answer by 1.

Finally, return the answer.

The time complexity is O(n times log_{10} M), and the space complexity is O(1). Here, n and M are the length of the array and the maximum value in the array, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n log n)O(1)Small n or quick verification of logic
Positional Digit CountingO(log n)O(1)General case and expected interview solution
Digit Dynamic ProgrammingO(d * 10)O(d)When additional constraints or multiple queries are involved

Video Solution

Count Digit Appearances | Leetcode 3895 | Explanation With Code | Java • codewithsitaram • 63 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Count Digit Appearances easy or hard?
Most platforms classify this problem as Medium. The brute force idea is simple, but deriving the O(log n) positional formula requires understanding how digits repeat across number ranges.
Count Digit Appearances Python/Java solution
Both Python and Java implementations follow the same positional counting logic. Use a loop with factor *= 10 and compute higher, current, and lower values at each step. The algorithm runs in O(log n) time and uses constant extra space.
How to solve Count Digit Appearances in O(log n)?
Break the number into positional components using a factor (1, 10, 100...). For each position, compute higher = n / (factor * 10), current = (n / factor) % 10, and lower = n % factor. These values determine how many full cycles contribute occurrences of the target digit at that position.
What is the best approach for Count Digit Appearances?
The positional digit counting method is the most efficient approach. It analyzes each decimal position (ones, tens, hundreds) and calculates how many times the target digit appears using higher, current, and lower digit segments. This reduces the complexity to O(log n) time with constant space.
Is Count Digit Appearances asked at Google/Amazon/Meta?
Digit counting and positional analysis problems appear frequently in interviews at companies like Google and Amazon. Variants such as counting the number of digit '1's from 1 to n or counting digits in a range test mathematical reasoning and edge‑case handling.
What data structure is used in Count Digit Appearances?
The optimal approach relies on mathematical decomposition rather than complex data structures. Only a few integer variables are required to track higher digits, the current digit, and lower digits while iterating through each decimal position.
What is the time complexity of Count Digit Appearances?
The optimal solution runs in O(log n) time because it processes each digit position of the number once. Since an integer n has log10(n) digits, the algorithm iterates through those positions and performs constant-time calculations per position.

Ready to solve this problem?

Practice Count Digit Appearances with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays