Skip to content

2520. Count the Digits That Divide a Number

SourceWeekly Contest 326 Q1DifficultyEasyRating1260

Description

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

Solutions

Solution 1: Enumeration

Thinking

Count how many digits of \(\textit{num}\) divide \(\textit{num}\). There are at most ten digits, so enumerating them is enough.

Repeatedly take \(\textit{val} = \textit{num} \bmod 10\) and test \(\textit{num} \bmod \textit{val} = 0\). The input contains no zero, so division by zero does not arise.

We directly enumerate each digit \(\textit{val}\) of the integer \(\textit{num}\), and if \(\textit{val}\) can divide \(\textit{num}\), we add one to the answer.

After the enumeration, we return the answer.

The time complexity is \(O(\log \textit{num})\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def countDigits(self, num: int) -> int:
        ans, x = 0, num
        while x:
            x, val = divmod(x, 10)
            ans += num % val == 0
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int countDigits(int num) {
        int ans = 0;
        for (int x = num; x > 0; x /= 10) {
            if (num % (x % 10) == 0) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int countDigits(int num) {
        int ans = 0;
        for (int x = num; x > 0; x /= 10) {
            if (num % (x % 10) == 0) {
                ++ans;
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func countDigits(num int) (ans int) {
    for x := num; x > 0; x /= 10 {
        if num%(x%10) == 0 {
            ans++
        }
    }
    return
}

1
2
3
4
5
6
7
8
9
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int countDigits(int num) {
    int ans = 0;
    int cur = num;
    while (cur) {
        if (num % (cur % 10) == 0) {
            ans++;
        }
        cur /= 10;
    }
    return ans;
}

Solution 2

Thinking

Solution 1 extracts digits arithmetically. Converting \(\textit{num}\) to a decimal string and testing each character yields the same check; only the way digits are obtained changes.

1
2
3
4
5
6
7
8
9
function countDigits(num: number): number {
    let ans = 0;
    for (const s of num.toString()) {
        if (num % Number(s) === 0) {
            ans++;
        }
    }
    return ans;
}

1
2
3
4
5
6
7
8
9
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
    }
}

Comments