Problem Description

A Harshad number is an integer that is divisible by the sum of its digits.

Given an integer x, you need to:

1. Calculate the sum of all digits in x
2. Check if x is divisible by this sum
3. If x is divisible by the sum (meaning x is a Harshad number), return the sum of digits
4. If x is not divisible by the sum (meaning x is not a Harshad number), return -1

For example:

• If x = 18: The sum of digits is 1 + 8 = 9. Since 18 is divisible by 9 (18 ÷ 9 = 2), it's a Harshad number, so return 9.
• If x = 19: The sum of digits is 1 + 9 = 10. Since 19 is not divisible by 10, it's not a Harshad number, so return -1.

The solution iterates through each digit of x by repeatedly taking the remainder when divided by 10 (y % 10) to get the last digit, adding it to the sum s, then removing the last digit by integer division (y //= 10). After calculating the sum of all digits, it checks if x % s == 0 to determine whether to return s or -1.

Intuition

The problem asks us to determine if a number is divisible by the sum of its digits. This naturally breaks down into two steps: first, we need to find the sum of the digits, and second, we need to check divisibility.

To extract digits from a number, we can use the mathematical property that the rightmost digit of any number can be obtained using the modulo operation % 10. For instance, 123 % 10 = 3 gives us the last digit. After extracting a digit, we can remove it from the number using integer division // 10, which shifts all digits one position to the right (essentially removing the last digit). For example, 123 // 10 = 12.

By repeatedly applying these two operations in a loop, we can extract all digits one by one from right to left:

• Extract the last digit using y % 10
• Add it to our running sum
• Remove the last digit using y // 10
• Continue until no digits remain (when y becomes 0)

Once we have the sum of all digits, checking if the original number is a Harshad number is straightforward - we simply use the modulo operator again: if x % sum == 0, then x is evenly divisible by the sum of its digits.

The elegance of this approach lies in using basic arithmetic operations (% and //) to both decompose the number into its digits and verify the Harshad property, making it efficient with O(log n) time complexity where n is the number of digits.

Learn more about Math patterns.

Solution Approach

The solution uses a simulation approach to calculate the sum of digits and check the Harshad property.

We initialize two variables:

• s = 0: to store the sum of digits
• y = x: a copy of the input number to manipulate without losing the original value

The core algorithm uses a while loop that continues as long as y has remaining digits (i.e., y > 0):

while y:
    s += y % 10    # Extract and add the last digit to sum
    y //= 10       # Remove the last digit

Let's trace through an example with x = 123:

• Initially: s = 0, y = 123
• First iteration: s = 0 + (123 % 10) = 0 + 3 = 3, then y = 123 // 10 = 12
• Second iteration: s = 3 + (12 % 10) = 3 + 2 = 5, then y = 12 // 10 = 1
• Third iteration: s = 5 + (1 % 10) = 5 + 1 = 6, then y = 1 // 10 = 0
• Loop ends since y = 0

After calculating the sum s = 6, we check if the original number is divisible by this sum:

return s if x % s == 0 else -1

For x = 123 and s = 6: Since 123 % 6 = 3 (not zero), we return -1.

The time complexity is O(log₁₀ x) because the number of digits in x is proportional to log₁₀ x. The space complexity is O(1) as we only use a constant amount of extra space for variables s and y.

Example Walkthrough

Let's walk through the solution with x = 12:

Step 1: Initialize variables

• s = 0 (to store sum of digits)
• y = 12 (copy of x to manipulate)

Step 2: Extract and sum digits

First iteration:

• Extract last digit: y % 10 = 12 % 10 = 2
• Add to sum: s = 0 + 2 = 2
• Remove last digit: y = 12 // 10 = 1

Second iteration:

• Extract last digit: y % 10 = 1 % 10 = 1
• Add to sum: s = 2 + 1 = 3
• Remove last digit: y = 1 // 10 = 0

Loop ends (y = 0)

Step 3: Check Harshad property

• Sum of digits: s = 3
• Check divisibility: 12 % 3 = 0
• Since remainder is 0, 12 is divisible by 3

Result: Return 3 (the sum of digits)

This confirms that 12 is a Harshad number because it's divisible by the sum of its digits (12 ÷ 3 = 4).

Solution Implementation

Time and Space Complexity

The time complexity is O(log x), where x is the input integer. This is because the while loop iterates through each digit of the number x. The number of digits in x is ⌊log₁₀(x)⌋ + 1, which is proportional to log x. In each iteration, we perform constant time operations (modulo, integer division, and addition).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for the variables s and y, regardless of the size of the input x. No additional data structures that grow with the input size are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Division by Zero Error

The most critical pitfall in this solution is the potential for division by zero when checking x % digit_sum. This occurs when the input x = 0, resulting in digit_sum = 0, which causes a ZeroDivisionError when evaluating x % digit_sum.

Solution: Add a special case check for zero:

def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
    # Handle edge case: x = 0
    if x == 0:
        return 0  # 0 is considered a Harshad number (0 is divisible by 0)
  
    digit_sum = 0
    temp_num = x
  
    while temp_num > 0:
        digit_sum += temp_num % 10
        temp_num //= 10
  
    return digit_sum if x % digit_sum == 0 else -1

2. Modifying the Original Value

A common mistake is directly modifying x instead of using a temporary variable:

# WRONG: This destroys the original value
while x:
    digit_sum += x % 10
    x //= 10  # Original x is now 0!

# Can't check x % digit_sum anymore since x is 0

Solution: Always create a copy of the input for manipulation:

temp_num = x  # Preserve original value
while temp_num > 0:
    digit_sum += temp_num % 10
    temp_num //= 10

3. Handling Negative Numbers

The problem doesn't explicitly state whether negative numbers are valid inputs. Using the modulo operator with negative numbers in Python can produce unexpected results.

Solution: Either work with the absolute value or add validation:

def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
    # Option 1: Work with absolute value
    abs_x = abs(x)
    digit_sum = 0
    temp_num = abs_x
  
    while temp_num > 0:
        digit_sum += temp_num % 10
        temp_num //= 10
  
    # Check divisibility with original number
    return digit_sum if x % digit_sum == 0 else -1

4. Integer Overflow in Other Languages

While Python handles arbitrary precision integers, implementing this in languages like C++ or Java requires consideration of integer overflow for very large numbers.

Solution for other languages: Use appropriate data types (like long long in C++) or add overflow checks when necessary.