Count the Digits That Divide a Number solution and explanation
TCS
Google
9 more videos on this problem
Count the Digits That Divide a Number | LeetCode 2520 | CppCodeClips with Abhishek Ranjan · 3:55 · 734 views
LeetCode 2520. Count the Digits That Divide a Number - Interview Prep Ep 124Fisher Coder · 6:54 · 676 views
Leetcode 2520 Count the Digits That Divide a Number (Java) - Leetcode Contest 326TheAnalyticGuy · 2:07 · 609 views
Leetcode 2520: Count the Digits That Divide a NumberAlgorithms Casts · 2:14 · 415 views
2520. Count the Digits That Divide a Number | LeetCode | C++ | Beginner Friendly SolutionDeep Tech · 4:18 · 287 views
2520. Count the Digits That Divide a Number (Leetcode Easy)Programming Live with Larry · 2:22 · 184 views
Count the Digits That Divide a Number | LeetCode 2520 Explained in C++ 🚀 | Beginner FriendlyRaniPatel16 · 7:15 · 21 views
Count the Digits that Divide a Number. Leetcode 2520.LogicLayerYT99 · 7:02 · 18 views
Count Digits That Divide a Number (LeetCode 2520) | Step-by-Step Solutionansh patel · 3:04 · 15 views
LeetCode 2520 - Count the Digits That Divide a Number | C++ Solution 🚀Dhruva Tajapara · 6:34 · 15 views
The problem
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.
def count_dividing_digits(num):
count = 0
original = num
while num > 0:
digit = num % 10
if digit != 0 and original % digit == 0:
count += 1
num //= 10
return count
num = 1248
print(count_dividing_digits(num))public class Main {
public static int countDividingDigits(int num) {
int count = 0;
int original = num;
while (num > 0) {
int digit = num % 10;
if (digit != 0 && original % digit == 0) {
count++;
}
num /= 10;
}
return count;
}
public static void main(String[] args) {
int num = 121;
System.out.println(countDividingDigits(num));
}
}#include <iostream>
using namespace std;
int countDividingDigits(int num) {
int count = 0;
int original = num;
while (num > 0) {
int digit = num % 10;
if (digit != 0 && original % digit == 0) {
count++;
}
num /= 10;
}
return count;
}
int main() {
int num = 1248;
cout << countDividingDigits(num) << endl;
return 0;
}function countDividingDigits(num) {
let count = 0;
let original = num;
while (num > 0) {
let digit = num % 10;
if (digit !== 0 && original % digit === 0) {
count++;
}
num = Math.floor(num / 10);
}
return count;
}
let num = 1248;
console.log(countDividingDigits(num));#include <stdio.h>
int countDividingDigits(int num) {
int count = 0;
int original = num;
while (num > 0) {
int digit = num % 10;
if (digit != 0 && original % digit == 0) {
count++;
}
num /= 10;
}
return count;
}
int main() {
int num = 121;
printf("%d\n", countDividingDigits(num));
return 0;
}using System;
public class Program {
public static int CountDividingDigits(int num) {
int count = 0;
int original = num;
while (num > 0) {
int digit = num % 10;
if (digit != 0 && original % digit == 0) {
count++;
}
num /= 10;
}
return count;
}
public static void Main() {
int num = 7;
Console.WriteLine(CountDividingDigits(num));
}
}In Python, we use a while loop to iterate over the digits by continually taking the modulus by 10. We check if each digit divides the original number, increasing the count if it does, and removing the last digit at each step.
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.
def count_dividing_digits(num):
count = 0
for digit in str(num):
if digit != '0' and num % int(digit) == 0:
count += 1
return count
num = 1248
print(count_dividing_digits(num))public class Main {
public static int countDividingDigits(int num) {
String str = Integer.toString(num);
int count = 0;
for (char ch : str.toCharArray()) {
int digit = ch - '0';
if (digit != 0 && num % digit == 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int num = 121;
System.out.println(countDividingDigits(num));
}
}#include <iostream>
#include <string>
int countDividingDigits(int num) {
std::string str = std::to_string(num);
int count = 0;
for (char ch : str) {
int digit = ch - '0';
if (digit != 0 && num % digit == 0) {
count++;
}
}
return count;
}
int main() {
int num = 1248;
std::cout << countDividingDigits(num) << std::endl;
return 0;
}function countDividingDigits(num) {
let count = 0;
let str = num.toString();
for (let ch of str) {
let digit = parseInt(ch, 10);
if (digit !== 0 && num % digit === 0) {
count++;
}
}
return count;
}
let num = 1248;
console.log(countDividingDigits(num));#include <stdio.h>
int countDividingDigits(int num) {
char buffer[12];
sprintf(buffer, "%d", num);
int count = 0;
for (int i = 0; buffer[i] != '\0'; ++i) {
int digit = buffer[i] - '0';
if (digit != 0 && num % digit == 0) {
count++;
}
}
return count;
}
int main() {
int num = 121;
printf("%d\n", countDividingDigits(num));
return 0;
}using System;
public class Program {
public static int CountDividingDigits(int num) {
string str = num.ToString();
int count = 0;
foreach (char ch in str) {
int digit = ch - '0';
if (digit != 0 && num % digit == 0) {
count++;
}
}
return count;
}
public static void Main() {
int num = 7;
Console.WriteLine(CountDividingDigits(num));
}
}Python's implementation leverages its dynamic typing to seamlessly convert between types, iterating over stringified digits and checking divisibility by converting back to integer easily.
Time Complexity: O(d), where d is the number of digits.
Space Complexity: O(d), due to string conversion.
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).
function countDigits(num: number): number {
let ans = 0;
for (let x = num; x; x = (x / 10) | 0) {
if (num % (x % 10) === 0) {
++ans;
}
}
return ans;
}func countDigits(num int) (ans int) {
for x := num; x > 0; x /= 10 {
if num%(x%10) == 0 {
ans++
}
}
return
}impl Solution {
pub fn count_digits(num: i32) -> i32 {
let mut ans = 0;
let mut cur = num;
while cur != 0 {
if num % (cur % 10) == 0 {
ans += 1;
}
cur /= 10;
}
ans
}
}Approach 4: Default Approach
function countDigits(num: number): number {
let ans = 0;
for (const s of num.toString()) {
if (num % Number(s) === 0) {
ans++;
}
}
return ans;
}impl Solution {
pub fn count_digits(num: i32) -> i32 {
num.to_string()
.chars()
.filter(|&c| c != '0')
.filter(|&c| num % (c.to_digit(10).unwrap() as i32) == 0)
.count() as i32
}
}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 | – |
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. |
Frequently asked questions
Is Count the Digits That Divide a Number easy or hard?
Count the Digits That Divide a Number is classified as an Easy problem. It focuses on basic digit manipulation, modulus arithmetic, and careful handling of the zero digit during divisibility checks.
How to solve Count the Digits That Divide a Number in O(n)?
Treat n as the number of digits in the integer. Iterate through every digit either by repeatedly applying modulus and division operations or by converting the number to a string. For each digit d, check if d != 0 and num % d == 0, then increment the count.
What is the best approach for Count the Digits That Divide a Number?
The iterative modulus approach is the best solution. Extract each digit using num % 10 and check if the original number is divisible by that digit. This method runs in O(d) time where d is the number of digits and uses O(1) extra space, making it optimal.
What data structure is used in Count the Digits That Divide a Number?
No complex data structure is required. The solution relies on basic arithmetic operations such as modulus and division. Some implementations convert the number into a string, which allows iteration over characters.
What is the time complexity of Count the Digits That Divide a Number?
The time complexity is O(d), where d is the number of digits in the integer. Each digit is processed exactly once, and the main operation performed is a modulus check to test divisibility.
Count the Digits That Divide a Number Python or Java solution approach
Both Python and Java implementations typically iterate through the digits and apply a modulus check against the original number. The arithmetic approach uses repeated digit extraction with % and / operations, achieving O(d) time and constant extra space.
Is Count the Digits That Divide a Number asked at Google, Amazon, or Meta?
This problem is categorized as an easy math-based question and commonly appears in coding practice platforms and entry-level interview preparation. Variations involving digit extraction and divisibility checks are frequently used in screening rounds.