Leetcode 2520: Count the Digits That Divide a Number
Given a positive integer
num, determine how many of its digits divide num without leaving a remainder. In other words, for each digit in num, check if num % digit == 0 and count how many digits satisfy this condition.Problem
Approach
Steps
Complexity
Input: You are given an integer `num`. You need to find how many of its digits divide the number `num` evenly.
Example: num = 123
Constraints:
• 1 <= num <= 10^9
• num does not contain the digit 0
Output: Return the number of digits in `num` that divide `num` without leaving a remainder.
Example: Output: 2
Constraints:
• The output should be an integer representing the number of digits that divide the number.
Goal: The goal is to count how many digits of `num` divide `num` evenly.
Steps:
• Convert `num` to a string to access each digit.
• For each digit in the number, check if `num % digit == 0`.
• Count how many digits satisfy the condition.
Goal: The number `num` is a positive integer with up to 9 digits.
Steps:
• The integer `num` is guaranteed to have no zeroes as its digits.
• The value of `num` is between 1 and 10^9.
Assumptions:
• All digits in `num` are non-zero.
• Input: num = 123
• Explanation: For `123`, the digits `1` and `3` divide `123`, but `2` does not. So, the answer is 2.
• Input: num = 256
• Explanation: For `256`, the digits `2`, `5`, and `6` divide `256`. So, the answer is 3.
Approach: To solve the problem, we will convert the number into its digits, check each digit for divisibility, and count how many satisfy the condition.
Observations:
• The problem requires iterating through the digits of a number and checking divisibility.
• Converting the number to a string allows easy access to each digit, and the modulo operation can be used to check divisibility.
Steps:
• Convert the number to a string or array of digits.
• For each digit, check if it divides the original number.
• Keep a counter to track how many digits divide the number evenly.
• Return the counter as the result.
Empty Inputs:
• This problem does not require handling empty inputs as `num` is always a positive integer.
Large Inputs:
• The solution must be efficient enough to handle the largest possible value of `num` (up to 10^9).
Special Values:
• The number will not contain the digit zero, so no need to handle division by zero.
Constraints:
• Ensure that the solution runs within time limits for the largest values of `num`.
int countDigits(int num) {
int res = 0;
for (int n = num; n > 0; n /= 10)
res += num % (n % 10) == 0;
return res;
}
1 : Function Definition
int countDigits(int num) {
Define the function `countDigits` that takes an integer `num` as input and returns the count of digits that divide `num` evenly.
2 : Variable Initialization
int res = 0;
Initialize a variable `res` to 0. This variable will hold the count of digits that divide `num` evenly.
3 : Loop
for (int n = num; n > 0; n /= 10)
Start a `for` loop that iterates through each digit of `num`. The variable `n` starts as `num` and is divided by 10 in each iteration to move to the next digit.
4 : Condition Check
res += num % (n % 10) == 0;
Check if the current digit `n % 10` divides `num` evenly (i.e., `num % digit == 0`). If true, increment the result `res`.
5 : Return Statement
return res;
Return the final count of digits that divide `num` evenly, stored in `res`.
Best Case: O(d), where d is the number of digits in `num`.
Average Case: O(d), where d is the number of digits in `num`.
Worst Case: O(d), where d is the number of digits in `num`.
Description: The time complexity is linear in terms of the number of digits in `num`, which is at most 9.
Best Case: O(d), where d is the number of digits in `num`.
Worst Case: O(d), where d is the number of digits in `num`.
Description: We need space proportional to the number of digits in `num` to store them temporarily.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus