2520. Count the Digits That Divide a Number
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:
- Obtain the last digit of
num
by using thedivmod
operation with10
, which gives us both the quotient and the remainder. The remainder here is the last digit which we will check for divisibility. - If
num
is divisible by this digit (checked bynum % val == 0
), we increment our answer count. - 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.
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:
- Initialize
ans
as0
which will hold our count of valid digits andx
asnum
to begin processing the digits. - Use a while loop that continues as long as
x
is greater than0
. This loop will help us process each digit from right to left until we have iterated through all the digits ofnum
. - Inside the loop, the
divmod(x, 10)
function is used to dividex
by10
.divmod
returns two values: the quotient and the remainder. The quotient is stored back inx
for the next iteration, effectively removing the last digit fromx
. The remainder, which is the last digit ofx
, is stored inval
. - An inline conditional statement checks if the current digit
val
dividesnum
evenly (num % val == 0
). If the condition is true, it increments theans
counter by1
. - 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 innum
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
- Initialize
ans = 0
as the count of valid digits that dividenum
andx = num
which in our case isx = 252
. - Set up a while loop that continues while
x > 0
. Beginning withx = 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
.
- The while loop ends because
x
is now0
, and we have processed all digits. We return the final countans
, which is2
.
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
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.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!