Harshad Number

Harshad Number

What is this problem about?

The Harshad Number interview question (also known as a Niven number) asks you to check if a given integer is divisible by the sum of its digits. If the number is divisible, you typically return the sum of the digits; otherwise, you return -1. For example, the number 18 is a Harshad number because $1 + 8 = 9$, and 18 is divisible by 9.

Why is this asked in interviews?

Microsoft and other companies use this "Easy" level problem to assess a candidate's basic arithmetic fluency and their ability to implement simple mathematical rules. It tests the core skill of digit manipulation, which is a prerequisite for more complex string and number-based algorithms. It also evaluates attention to detail regarding return types and edge cases like zero or single-digit numbers.

Algorithmic pattern used

This problem follows a simple Math interview pattern. The logic involves two steps:

1. Digit Summation: Extract each digit of the number using a while loop with the modulo operator (number % 10) and then reduce the number using integer division (number / 10).
2. Divisibility Check: Perform a simple check using the modulo operator to see if the original number divided by the sum has a remainder of zero.

Example explanation

Take the number 21:

1. Extract digits: 1 and 2.
2. Sum: $1 + 2 = 3$.
3. Check: $21 \div 3 = 7$ with remainder 0.
4. Result: 21 is a Harshad number, return 3.

Take the number 15:

1. Extract digits: 5 and 1.
2. Sum: $5 + 1 = 6$.
3. Check: $15 \div 6 = 2$ with remainder 3.
4. Result: Not a Harshad number, return -1.

Common mistakes candidates make

• Destroying the Input: Modifying the original input variable during the digit sum phase and then trying to use it for the final divisibility check. Always store the original value in a temporary variable.
• Incorrect Modulo Logic: Confusing the dividend and the divisor in the final check (e.g., checking sum % num instead of num % sum).
• String Conversion: Using str(n) in Python or n.toString() in JS to sum digits. While valid, it’s considered less "algorithmic" than the mathematical approach.

Interview preparation tip

Always master the "Digit Extraction" template: while num > 0: digit = num % 10; sum += digit; num //= 10;. This snippet is the foundation for dozens of coding problems. Being able to write it flawlessly in seconds shows your comfort with basic low-level logic.