Teaching Kids Programming – Count the Digits That Divide a Number (Three Algorithms)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^9
num does not contain 0 as one of its digits.

Count the Digits That Divide a Number (Using Counter)

We can use the Counter aka Hash Map to count the digits and their frequencies, then we accumulate the frequencies if the digit divides.

1
2
3
4
5
6
7
8

class Solution:
    def countDigits(self, num: int) -> int:
        ans = 0
        c = Counter(str(num))
        for i, v in c.items():
            if num % int(i) == 0:
                ans += v
        return ans

class Solution:
    def countDigits(self, num: int) -> int:
        ans = 0
        c = Counter(str(num))
        for i, v in c.items():
            if num % int(i) == 0:
                ans += v
        return ans

Time/space complexity is O(N) where N is the number of the digits for the number i.e. where n is the given number.

Count the Digits That Divide a Number (Converting to String – Left to Right)

We can convert the number to string, and then iterate over the string, and check each digit and increment the answer if it divides.

1
2
3
4
5
6
7

class Solution:
    def countDigits(self, num: int) -> int:
        ans = 0
        for _, v in enumerate(str(num)):
            if num % int(v) == 0:
                ans += 1
        return ans

class Solution:
    def countDigits(self, num: int) -> int:
        ans = 0
        for _, v in enumerate(str(num)):
            if num % int(v) == 0:
                ans += 1
        return ans

Same time/space complexity because we need to store the string version of the number.

Count the Digits That Divide a Number (From Right to Left)

We can check from the Least Significant Digit (LSB), and this requires math only.

1
2
3
4
5
6
7
8
9

class Solution:
    def countDigits(self, num: int) -> int:
        ans = 0
        n = num
        while n:
            if num % (n % 10) == 0:
                ans += 1
            n //= 10
        return ans

class Solution:
    def countDigits(self, num: int) -> int:
        ans = 0
        n = num
        while n:
            if num % (n % 10) == 0:
                ans += 1
            n //= 10
        return ans

The time complexity is O(N) and the space complexity is O(1). N is the number of the digits.

–EOF (The Ultimate Computing & Technology Blog) —