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 <= 109num does not contain 0 as one of its digits.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.
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.
Time Complexity: O(d), where d is the number of digits in the number.
Space Complexity: O(1), as no additional space is used.
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.
Time Complexity: O(d), where d is the number of digits.
Space Complexity: O(d), used for string storage.
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).
TypeScript
Rust
| 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 | — |
| 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. |
Leetcode 2520 Count the Digits That Divide a Number hindi • ThinkCode • 797 views views
Watch 9 more video solutions →Practice Count the Digits That Divide a Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor