Jobs

Interviews

Discussions

Count the Digits That Divide a Number

Easy

Google

2 views

You are given an integer num. Your task is to return the number of digits in num that divide num.

An integer val is said to divide num if num % 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 <= 10^9
num does not contain 0 as one of its digits.

Could you implement a function to solve this problem efficiently?

Count the Digits That Divide a Number

Easy

Google

2 views

You are given an integer num. Your task is to return the number of digits in num that divide num.

An integer val is said to divide num if num % 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 <= 10^9
num does not contain 0 as one of its digits.

Could you implement a function to solve this problem efficiently?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input number? Can it be zero or negative?
If a digit is zero, should it be considered a divisor?
If the number is divisible by the same digit multiple times (e.g., 12 divides by 1 twice), should I count each instance?
Should the return value be an integer representing the count, or is there a specific format I need to adhere to?
Are there any specific error conditions I need to handle or exceptions I should throw if the input is invalid?

Brute Force Solution

Approach

The brute force method here means checking every single digit of the number and testing it to see if it divides evenly into the original number. We'll go through each digit one by one and perform a division. We then count how many divisions result in a whole number with no remainder.

Here's how the algorithm would work step-by-step:

Take the given number.
Look at each digit in the number, one at a time.
For each digit, see if it divides evenly into the original number. That is, does the division have a remainder of zero?
If the digit does divide evenly into the original number, count it.
After checking all the digits, report the total count of digits that divided evenly.

Code Implementation

def count_digits_that_divide(number):
    number_string = str(number)
    count = 0

    for digit_char in number_string:
        digit = int(digit_char)

        # Avoid division by zero
        if digit == 0:
            continue

        # Checking if the digit divides evenly into the original number
        if number % digit == 0:

            # Increment the count if it divides evenly
            count += 1

    return count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each digit of the input number once. Let n be the number of digits in the input number. For each digit, it performs a constant time operation (division). Therefore, the time complexity is directly proportional to the number of digits, resulting in a time complexity of O(n).

Space Complexity

O(1) – The provided solution iterates through the digits of the input number, but it does not create any auxiliary data structures that scale with the input size. It only uses a few constant space variables, such as the original number itself and a counter for tracking how many digits divide evenly. Therefore, the space complexity is constant, regardless of the number of digits in the input number. In other words, the auxiliary space used does not depend on the size of the input.

Optimal Solution

Approach

The goal is to count how many digits of a number evenly divide the number itself. We achieve this by examining each digit individually and checking if it's a divisor.

Here's how the algorithm would work step-by-step:

First, remember the original number. This will be used for the division checks.
Convert the number into a string so you can easily look at each digit one at a time.
Go through each character (digit) in the string.
Convert the digit character back into a regular number.
Make sure the digit is not zero because dividing by zero is not allowed.
Check if the original number can be divided evenly by this digit (meaning the remainder is zero).
If it divides evenly, then increase your count.
After checking every digit, the final count is the answer.

Code Implementation

def count_the_digits_that_divide_a_number(number):
    original_number = number
    number_as_string = str(number)
    count = 0

    for digit_character in number_as_string:
        digit = int(digit_character)

        # Avoid division by zero
        if digit == 0:
            continue

        # Ensure the original number is divisible by the digit
        if original_number % digit == 0:
            count += 1

    return count

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is iterating through the digits of the input number num, which we represent as a string. Let n be the number of digits in num. We iterate through each of these n digits once. Inside the loop, the operations (digit conversion, division check) take constant time. Therefore, the overall time complexity is directly proportional to the number of digits, resulting in O(n).

Space Complexity

O(1) – The algorithm converts the input number to a string to iterate through its digits. The space used for this string, as well as for the digit variable and the count variable, is proportional to the number of digits in the input number. However, because the number of digits is limited by the size of the integer type (e.g., 32-bit or 64-bit), it can be considered constant. Thus, the space used is constant and does not depend on an arbitrarily large input size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Input number is 0	Handle the zero case separately to avoid division by zero errors by returning 0.
Input number is a single-digit number	The digit divides the number if it is not zero, and the number is not zero.
Input number contains the digit 0	The code should avoid division by zero when checking if the digit divides the number.
Input number is a very large number (potential overflow)	Ensure the algorithm uses a data type that can accommodate the number without overflow; consider using strings.
All digits divide the number	The solution should correctly count all the digits in this scenario.
No digits divide the number	The solution should return 0 in this case.
Negative input numbers	The problem statement does not mention anything about negative inputs; so, one can assume we only handle positive integers, or clarify this assumption with the interviewer, or take the absolute value of the number.
Number with repeated digits, some of which divide and some do not	The solution needs to ensure each digit occurrence is checked only once and counted accordingly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input number? Can it be zero or negative?
If a digit is zero, should it be considered a divisor?
If the number is divisible by the same digit multiple times (e.g., 12 divides by 1 twice), should I count each instance?
Should the return value be an integer representing the count, or is there a specific format I need to adhere to?
Are there any specific error conditions I need to handle or exceptions I should throw if the input is invalid?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the given number.
Look at each digit in the number, one at a time.
For each digit, see if it divides evenly into the original number. That is, does the division have a remainder of zero?
If the digit does divide evenly into the original number, count it.
After checking all the digits, report the total count of digits that divided evenly.

Code Implementation

def count_digits_that_divide(number):
    number_string = str(number)
    count = 0

    for digit_char in number_string:
        digit = int(digit_char)

        # Avoid division by zero
        if digit == 0:
            continue

        # Checking if the digit divides evenly into the original number
        if number % digit == 0:

            # Increment the count if it divides evenly
            count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to count how many digits of a number evenly divide the number itself. We achieve this by examining each digit individually and checking if it's a divisor.

Here's how the algorithm would work step-by-step:

First, remember the original number. This will be used for the division checks.
Convert the number into a string so you can easily look at each digit one at a time.
Go through each character (digit) in the string.
Convert the digit character back into a regular number.
Make sure the digit is not zero because dividing by zero is not allowed.
Check if the original number can be divided evenly by this digit (meaning the remainder is zero).
If it divides evenly, then increase your count.
After checking every digit, the final count is the answer.

Code Implementation

def count_the_digits_that_divide_a_number(number):
    original_number = number
    number_as_string = str(number)
    count = 0

    for digit_character in number_as_string:
        digit = int(digit_character)

        # Avoid division by zero
        if digit == 0:
            continue

        # Ensure the original number is divisible by the digit
        if original_number % digit == 0:
            count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input number is 0	Handle the zero case separately to avoid division by zero errors by returning 0.
Input number is a single-digit number	The digit divides the number if it is not zero, and the number is not zero.
Input number contains the digit 0	The code should avoid division by zero when checking if the digit divides the number.
Input number is a very large number (potential overflow)	Ensure the algorithm uses a data type that can accommodate the number without overflow; consider using strings.
All digits divide the number	The solution should correctly count all the digits in this scenario.
No digits divide the number	The solution should return 0 in this case.
Negative input numbers	The problem statement does not mention anything about negative inputs; so, one can assume we only handle positive integers, or clarify this assumption with the interviewer, or take the absolute value of the number.
Number with repeated digits, some of which divide and some do not	The solution needs to ensure each digit occurrence is checked only once and counted accordingly.