Count the Digits That Divide a Number - Solution & Explanation
Problem Statement
Given an integer num, return the number of digits in num that divide num.
An integer val divides nums if nums % val == 0.
Example 1:
Input: num = 7 Output: 1 Explanation: 7 divides itself, hence the answer is 1.
Example 2:
Input: num = 121 Output: 2 Explanation: 121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2.
Example 3:
Input: num = 1248 Output: 4 Explanation: 1248 is divisible by all of its digits, hence the answer is 4.
Constraints:
1 <= num <= 109numdoes not contain0as one of its digits.
Approach Overview
Problem Overview: Given an integer num, count how many of its digits evenly divide the number. For each digit d in the number, check if num % d == 0. Ignore digits that are zero since division by zero is undefined.
Approach 1: Iterative Check Using Modulus (O(d) time, O(1) space)
This approach works directly with the number using basic math operations. Repeatedly extract the last digit using digit = temp % 10, then remove it with integer division temp /= 10. For each extracted digit, check if it is non-zero and whether num % digit == 0. If the condition holds, increment the count.
The key insight is that you only need to examine each digit once. Modulus operations provide both digit extraction and divisibility checks efficiently. Since the number of digits is d = log10(num), the loop runs d times. This keeps the time complexity O(d) and space complexity O(1). This method is preferred when you want minimal memory usage and direct arithmetic operations.
Approach 2: Leveraging String Conversion (O(d) time, O(d) space)
Instead of repeatedly extracting digits mathematically, convert the integer into a string. Iterate over each character, convert it back to an integer digit, and check whether it divides the original number. Skip characters representing 0 to avoid division errors.
This approach trades arithmetic digit extraction for easier iteration using string traversal. The divisibility check still uses the modulo operation from math. Time complexity remains O(d) because each digit is processed once. Space complexity becomes O(d) due to the temporary string representation.
Recommended for interviews: The iterative modulus approach is the expected solution. It demonstrates understanding of digit extraction, modulo arithmetic, and constant-space iteration. The string approach is perfectly valid but slightly less optimal in space. Showing the arithmetic solution first signals strong fundamentals with number manipulation.
Approach 1: Approach 1: Iterative Check Using Modulus
In this approach, we will convert the integer into a string to access each digit easily. We'll iterate through each digit, convert it back to an integer, and check if it divides the number using the modulus operation. This straightforward method handles each digit one by one and checks for divisibility.
The C solution makes use of a loop to repeatedly extract the last digit of the number using the modulus operator. It checks if this digit is a divisor of the original number. If so, it increases the count. Finally, it divides the number by 10 to remove the last digit and continues this process until all digits are checked.
Complexity
Time Complexity: O(d), where d is the number of digits in the number.
Space Complexity: O(1), as no additional space is used.
Approach 2: Approach 2: Leveraging String Conversion
This approach involves converting the number to a string and iterating over each character. By converting each character back to an integer, we can easily check if it divides the original number using the modulus operation. This simplifies digit handling, given the ease of iterating over strings in many programming languages.
Utilizes string manipulation functions to handle each digit. The integer is converted to a string form, facilitating easy conversion of individual characters back to integers for modulus checks.
Complexity
Time Complexity: O(d), where d is the number of digits.
Space Complexity: O(d), used for string storage.
Approach 3: Enumeration
We directly enumerate each digit val of the integer num, and if val can divide num, we add one to the answer.
After the enumeration, we return the answer.
The time complexity is O(log num), and the space complexity is O(1).
Approach 4: Default Approach
Code
TypeScript
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Check Using Modulus | Time Complexity: O(d), where d is the number of digits in the number. |
| Approach 2: Leveraging String Conversion | Time Complexity: O(d), where d is the number of digits. |
| Enumeration | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Check Using Modulus | O(d) | O(1) | Best general solution. Uses constant space and direct digit extraction. |
| String Conversion and Iteration | O(d) | O(d) | Simpler to implement when readability matters more than space efficiency. |
Video Solution
Count the Digits That Divide a Number | LeetCode 2520 | Cpp • CodeClips with Abhishek Ranjan • 734 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count the Digits That Divide a Number easy or hard?
How to solve Count the Digits That Divide a Number in O(n)?
What is the best approach for Count the Digits That Divide a Number?
What data structure is used in Count the Digits That Divide a Number?
What is the time complexity of Count the Digits That Divide a Number?
Count the Digits That Divide a Number Python or Java solution approach
Is Count the Digits That Divide a Number asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Count the Digits That Divide a Number with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor