Scale Engineer

Count the Digits That Divide a Number

Easy
#2300Time: O(log10(num))Space: O(log10(num))1 company
Patterns
Math
Companies
tcs

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves converting the integer num into its string representation. Once we have the string, we can easily iterate through each character, which represents a digit. For each character, we convert it back to an integer and check if it divides the original number num.

Algorithm

  • Initialize a counter count to 0.
  • Convert the input integer num to its string representation, let's call it s.
  • Iterate through each character c in the string s.
  • For each character, convert it back to its integer value digit. In Java, this is c - '0'.
  • Check if the original num is divisible by digit (i.e., num % digit == 0).
  • If it is, increment the count.
  • After the loop finishes, return the count.

Walkthrough

The core idea is to leverage the simplicity of string manipulation to access the individual digits of the number. By converting the number to a string, we can use a simple loop to go through each digit one by one.

class Solution {    public int countDigits(int num) {        String numStr = Integer.toString(num);        int count = 0;        for (char c : numStr.toCharArray()) {            int digit = c - '0';            // According to constraints, num does not contain 0 as a digit,            // so we don't need to check for division by zero.            if (num % digit == 0) {                count++;            }        }        return count;    }}

Complexity

Time

O(log10(num))

Space

O(log10(num))

Trade-offs

Pros

  • The logic is very straightforward and easy to read and implement.

  • Leverages built-in language features for string conversion and iteration.

Cons

  • Uses extra space proportional to the number of digits to store the string representation.

  • Involves type conversions (integer to string, character to integer) which can have a minor performance overhead compared to pure arithmetic.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem