Count the Digits That Divide a Number

Count the Digits That Divide a Number

What is this problem about?

The Count the Digits That Divide a Number coding problem asks you to look at an integer num. You need to extract every digit that makes up num and check if num is divisible by that digit (i.e., num % digit == 0). You must count how many times this occurs. Note that if a digit appears multiple times, each occurrence is checked and counted separately.

Why is this asked in interviews?

This is a fundamental math interview pattern question used by Google and TCS. It tests a candidate's ability to perform digit extraction using modular arithmetic and their understanding of basic divisibility rules. It's a "warm-up" problem that checks for clean code, handling of zeros (if applicable), and efficient loops.

Algorithmic pattern used

The pattern is Digit Extraction using Modulo and Division.

1. Create a copy of the original number to extract digits.
2. While the copy is greater than zero:
   • Extract the last digit using % 10.
   • Check if original_num % digit == 0.
   • Increment the counter if true.
   • Remove the last digit from the copy using / 10 (integer division).

Example explanation

num = 1248

1. Digit 8: $1248 \% 8 = 0$. (Yes) -> Count = 1.
2. Digit 4: $1248 \% 4 = 0$. (Yes) -> Count = 2.
3. Digit 2: $1248 \% 2 = 0$. (Yes) -> Count = 3.
4. Digit 1: $1248 \% 1 = 0$. (Yes) -> Count = 4. Result: 4.

num = 121

1. Digit 1: $121 \% 1 = 0$. (Yes) -> Count = 1.
2. Digit 2: $121 \% 2 e 0$. (No).
3. Digit 1: $121 \% 1 = 0$. (Yes) -> Count = 2. Result: 2.

Common mistakes candidates make

• Modifying the number used for modulo: If you use num = num / 10 without keeping a copy of the original num, you won't be able to perform the divisibility check correctly.
• Division by zero: While the problem usually ensures digits are non-zero, in a general context, dividing by zero causes an error.
• Integer overflow: Not an issue here since digits are small, but always good to keep in mind when working with division.

Interview preparation tip

Master the n % 10 and n / 10 loop. It is the most common way to iterate through digits of a number in any programming language and is often faster and more memory-efficient than converting the number to a string.