Harshad Number

Difficulty: Easy | Acceptance: 83.30% | Paid: No Topics: Math

An integer divisible by the sum of its digits is said to be a Harshad number. You are given an integer x. Return the sum of the digits of x if x is a Harshad number, otherwise return -1.

• Examples
• Constraints
• Mathematical Approach
• String Conversion Approach
• Recursive Approach

Examples

Input: x = 18
Output: 9
Explanation: 
The sum of digits of x is 9. 18 is divisible by 9, so 18 is a Harshad number.

Input: x = 23
Output: -1
Explanation: 
The sum of digits of x is 5. 23 is not divisible by 5, so 23 is not a Harshad number.

Constraints

1 <= x <= 100

Mathematical Approach

Intuition Extract digits using modulo and division operations, sum them, then check if the original number is divisible by this sum.

Steps

• Initialize a sum variable to 0
• Extract each digit using modulo 10 and add to sum
• Divide the number by 10 to remove the last digit
• Repeat until number becomes 0
• Check if original number is divisible by the sum

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        original = x
        digit_sum = 0
        while x > 0:
            digit_sum += x % 10
            x //= 10
        return digit_sum if original % digit_sum == 0 else -1

Complexity

• Time: O(log₁₀ x) - number of digits in x
• Space: O(1) - constant extra space
• Notes: Most efficient approach with minimal memory overhead

String Conversion Approach

Intuition Convert the number to a string, iterate through each character, convert back to integer, sum all digits, then check divisibility.

Steps

• Convert the number to string representation
• Iterate through each character in the string
• Convert each character back to integer and accumulate sum
• Check if original number is divisible by the sum

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        digit_sum = sum(int(d) for d in str(x))
        return digit_sum if x % digit_sum == 0 else -1

Complexity

• Time: O(log₁₀ x) - number of digits in x
• Space: O(log₁₀ x) - space for string representation
• Notes: More readable but uses extra memory for string conversion

Recursive Approach

Intuition Use recursion to extract and sum digits by repeatedly taking the last digit and processing the remaining number.

Steps

• Base case: if number is 0, return 0
• Recursive case: return last digit plus sum of remaining digits
• Check if original number is divisible by the computed sum

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        def digit_sum(n):
            if n == 0:
                return 0
            return n % 10 + digit_sum(n // 10)
        
        s = digit_sum(x)
        return s if x % s == 0 else -1

Complexity

• Time: O(log₁₀ x) - number of digits in x
• Space: O(log₁₀ x) - recursion stack depth
• Notes: Elegant but uses call stack space; may cause stack overflow for very large numbers