2520. Count the Digits That Divide a Number

EasyMath
Leetcode Link

Problem Description

Given an integer num, the task is to find out how many of its own digits can divide the number itself without leaving a remainder. To clarify, for a digit d in num to be a valid divisor, the number num divided by this digit d should result in a whole number, meaning that num % d should equal 0. It is important to note that the integer num will not contain the digit 0, ensuring we avoid division by zero. You're expected to count all such digits that divide num and return this count as your answer.

Intuition

The basic idea for solving this problem is straightforward: go through each digit in the integer num and check if num can be divided by that digit without any remainder. We keep a count of all such digits that meet the criteria.

To implement this, we can use a while loop to iterate over the digits of num. In each iteration, we:

  1. Obtain the last digit of num by using the divmod operation with 10, which gives us both the quotient and the remainder. The remainder here is the last digit which we will check for divisibility.
  2. If num is divisible by this digit (checked by num % val == 0), we increment our answer count.
  3. We continue this process until we've checked all digits of num.

By following this process, we can count and return the number of digits in num that divide num itself.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

Solution Approach

The implementation of the provided solution makes use of a simple while loop and basic arithmetic operations to solve the problem. This approach does not require additional data structures, thus maintaining a low space complexity. Here's how the solution is implemented, step-by-step:

  1. Initialize ans as 0 which will hold our count of valid digits and x as num to begin processing the digits.
  2. Use a while loop that continues as long as x is greater than 0. This loop will help us process each digit from right to left until we have iterated through all the digits of num.
  3. Inside the loop, the divmod(x, 10) function is used to divide x by 10. divmod returns two values: the quotient and the remainder. The quotient is stored back in x for the next iteration, effectively removing the last digit from x. The remainder, which is the last digit of x, is stored in val.
  4. An inline conditional statement checks if the current digit val divides num evenly (num % val == 0). If the condition is true, it increments the ans counter by 1.
  5. Once all digits have been processed and the loop ends, the function returns the value of ans, which now represents the total count of digits in num that can divide it without a remainder.

By iterating through each digit and checking divisibility, the algorithm ensures that all possible divisors are considered. This approach is an example of enumeration, where every element in a set (in this case, every digit of an integer) is counted for its validity against a specific condition (divisibility). Hence, every digit is enumerated to determine whether it divides the original number.

This solution is efficient as it processes each digit once and performs a constant number of operations per digit, leading to a time complexity that is linear with respect to the number of digits in num.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach. Consider the integer num = 252. We need to find out how many of its digits can divide the number itself without leaving a remainder.

Following the solution approach step by step:

  1. Initialize ans = 0 as the count of valid digits that divide num and x = num which in our case is x = 252.
  2. Set up a while loop that continues while x > 0. Beginning with x = 252, we will iterate through each digit.

The first iteration goes as follows: 3. We use divmod(x, 10) to divide x by 10. For the first iteration, divmod(252, 10) returns (25, 2). We update x to 25 and val to 2. 4. We check if num % val == 0. Since 252 % 2 == 0, the condition is true, and we increment ans to 1.

The second iteration: 3. x has been updated to 25, and we perform divmod(25, 10) which gives us (2, 5). Now, x = 2 and val = 5. 4. Again, we check num % val. Here, 252 % 5 == 2, leaving a remainder. Therefore, we do not increment ans.

The third iteration: 3. Now with x = 2, when we use divmod(2, 10) we get (0, 2). We update x to 0 for the next iteration (which won't happen since x is now 0), and val = 2. 4. Checking num % val one last time, we find that 252 % 2 == 0. Since it divides evenly, we increment ans to 2.

  1. The while loop ends because x is now 0, and we have processed all digits. We return the final count ans, which is 2.

In this example, two of the digits (2 and 2) can divide 252 without a remainder. So the function would return 2.

Solution Implementation

1class Solution:
2    def countDigits(self, num: int) -> int:
3        # Initialize 'count' to keep track of the count of digits
4        count = 0
5      
6        # Make a copy of the input number for manipulation
7        temp_num = num
8      
9        # Iterate until the copied number is reduced to 0
10        while temp_num:
11            # Divide 'temp_num' by 10 to isolate the rightmost digit ('digit')
12            # and reduce 'temp_num' for the next iteration
13            temp_num, digit = divmod(temp_num, 10)
14          
15            # Avoid a division by zero and check if the digit divides 'num' without a remainder
16            if digit != 0 and num % digit == 0:
17                # If the digit divides 'num', increment the 'count'
18                count += 1
19      
20        # Finally, return the count of such digits
21        return count
22
1class Solution {
2    public int countDigits(int num) {
3        int count = 0; // Initialize count of digits
4
5        // Loop through each digit of the number
6        for (int current = num; current > 0; current /= 10) {
7            int digit = current % 10; // Get the last digit
8          
9            // Check if digit is non-zero and perfectly divides the num
10            if (digit != 0 && num % digit == 0) {
11                count++; // Increment count if condition is met
12            }
13        }
14      
15        return count; // Return the final count
16    }
17}
18
1class Solution {
2public:
3    // Function to count the number of digits in 'num' that are divisors of 'num'
4    int countDigits(int num) {
5        int count = 0; // Variable to store the count of digits that are divisors of 'num'
6        for (int current = num; current > 0; current /= 10) {
7            int digit = current % 10; // Extract the rightmost digit of 'current'
8          
9            // Avoid division by zero error when the digit is 0
10            if (digit == 0) continue;
11          
12            // Check if 'num' is divisible by 'digit'
13            if (num % digit == 0) {
14                ++count; // Increment the count if 'digit' is a divisor of 'num'
15            }
16        }
17        return count; // Return the final count of divisor digits
18    }
19};
20
1function countDigits(num: number): number {
2    let count = 0; // Initialize a variable to count the digits that meet the criteria
3    for (let current = num; current; current = Math.floor(current / 10)) { // Iterate over each digit of the number
4        let digit = current % 10; // Extract the current digit
5      
6        // Check if the original number is divisible by the current digit
7        // and ensure not to divide by 0
8        if (digit !== 0 && num % digit === 0) {
9            count++; // Increment count if the number is divisible by the digit
10        }
11    }
12    return count; // Return the total count of divisible digits
13}
14
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

The time complexity of the code is O(log num). This is because the while loop runs as many times as there are digits in num. The number of digits in a number increases with the logarithm of the number, hence the logarithmic complexity.

The space complexity of the code is O(1). The space used by the algorithm does not depend on the size of the input number num, as it only uses a fixed number of integer variables (ans, x, and val) regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫