LeetCode 3099 - Harshad Number

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to determine whether a given integer is a Harshad number. A Harshad number is an integer that is divisible by the sum of its digits.

We are given a single integer x, and we must perform two operations:

Compute the sum of all digits in x
Check whether x is divisible by that digit sum

If the divisibility condition is true, we return the digit sum itself. Otherwise, we return -1.

For example, if x = 18, the digits are 1 and 8, whose sum is 9. Since 18 % 9 == 0, the number is a Harshad number, so the answer is 9.

If x = 23, the digit sum is 2 + 3 = 5. Since 23 % 5 != 0, the number is not a Harshad number, so we return -1.

The constraints are very small:

1 <= x <= 100

This tells us several important things:

The input is always positive
The number contains at most three digits
Performance is not a concern because the search space is tiny
We do not need to worry about integer overflow

Even though the constraints are small, we should still aim for a clean and correct implementation.

An important edge case is a single digit number. Every non-zero single digit number is divisible by itself, so all numbers from 1 to 9 are Harshad numbers.

Another detail is that the problem guarantees x >= 1, so we never have to deal with division by zero when checking divisibility.

Approaches

Brute Force Approach

A brute force style solution would first convert the integer into a string, iterate through every character, convert each character back into an integer digit, and accumulate the digit sum.

After computing the sum, we check whether x % digit_sum == 0.

This approach is completely acceptable for the problem constraints because the input size is extremely small. It is simple, readable, and guaranteed to produce the correct result because every digit is examined exactly once.

The downside is that string conversion introduces some unnecessary overhead. While insignificant here, it is not the most direct mathematical solution.

Optimal Approach

The optimal approach uses pure arithmetic to compute the digit sum.

The key observation is that we can extract digits one at a time using:

digit = x % 10

and remove the last digit using:

x = x // 10

By repeatedly applying these operations, we can compute the sum of digits without converting the number into a string.

Once the digit sum is known, we simply test divisibility.

This approach is more idiomatic for digit manipulation problems and avoids extra string operations.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Converts number to string and iterates over digits
Optimal	O(d)	O(1)	Uses arithmetic digit extraction directly

Here, d represents the number of digits in x.

Algorithm Walkthrough

Store the original value of x because we will modify the number while extracting digits.
Initialize a variable called digit_sum to 0. This variable will accumulate the sum of all digits.
Repeatedly extract the last digit using x % 10.
Add the extracted digit to digit_sum.
Remove the last digit from x using integer division, x //= 10.
Continue until x becomes 0. At this point, every digit has been processed.
Check whether the original number is divisible by digit_sum.
If divisibility holds, return digit_sum.
Otherwise, return -1.

Why it works

The algorithm works because every decimal digit of a number can be isolated using modulo by 10, and removed using integer division by 10. Repeating this process guarantees that every digit contributes exactly once to the final sum.

Once the correct digit sum is computed, the Harshad condition is simply a divisibility check. Therefore, the algorithm always returns the correct answer.

Python Solution

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        original = x
        digit_sum = 0

        while x > 0:
            digit_sum += x % 10
            x //= 10

        if original % digit_sum == 0:
            return digit_sum

        return -1

The implementation starts by storing the original value because the variable x will be modified during digit extraction.

The while loop processes one digit per iteration. The expression x % 10 extracts the last digit, and x //= 10 removes it from the number.

After the loop finishes, digit_sum contains the sum of every digit in the original number.

The final if statement checks whether the original number is divisible by the digit sum. If it is, we return the digit sum itself. Otherwise, we return -1.

Go Solution

func sumOfTheDigitsOfHarshadNumber(x int) int {
    original := x
    digitSum := 0

    for x > 0 {
        digitSum += x % 10
        x /= 10
    }

    if original%digitSum == 0 {
        return digitSum
    }

    return -1
}

The Go implementation follows exactly the same arithmetic logic as the Python solution.

One small syntactic difference is that Go uses a for loop instead of Python's while loop. Integer division in Go is performed automatically when dividing integers, so x /= 10 behaves as expected.

Because the constraints are tiny, integer overflow is not a concern in either language.

Worked Examples

Example 1

Input:

x = 18

We begin with:

Variable	Value
original	18
x	18
digit_sum	0

Iteration 1

Operation	Result
x % 10	8
digit_sum	8
x //= 10	1

Iteration 2

Operation	Result
x % 10	1
digit_sum	9
x //= 10	0

The loop ends because x == 0.

Now we check:

18 % 9 == 0

This is true, so we return:

Example 2

Input:

x = 23

Initial state:

Variable	Value
original	23
x	23
digit_sum	0

Iteration 1

Operation	Result
x % 10	3
digit_sum	3
x //= 10	2

Iteration 2

Operation	Result
x % 10	2
digit_sum	5
x //= 10	0

The loop finishes.

Now evaluate:

23 % 5 == 3

This is not zero, so the number is not a Harshad number.

We return:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	We process each digit exactly once
Space	O(1)	Only a few integer variables are used

The running time depends on the number of digits in the input number. Each iteration removes one digit, so the loop executes exactly d times.

The algorithm uses constant extra memory because no auxiliary data structures are allocated.

Test Cases

solution = Solution()

assert solution.sumOfTheDigitsOfHarshadNumber(18) == 9      # Example Harshad number
assert solution.sumOfTheDigitsOfHarshadNumber(23) == -1     # Example non-Harshad number

assert solution.sumOfTheDigitsOfHarshadNumber(1) == 1       # Smallest valid input
assert solution.sumOfTheDigitsOfHarshadNumber(9) == 9       # Single digit Harshad number

assert solution.sumOfTheDigitsOfHarshadNumber(10) == 1      # Ends with zero
assert solution.sumOfTheDigitsOfHarshadNumber(12) == 3      # Divisible by digit sum
assert solution.sumOfTheDigitsOfHarshadNumber(11) == -1     # Not divisible by digit sum

assert solution.sumOfTheDigitsOfHarshadNumber(99) == 18     # Two digit Harshad number
assert solution.sumOfTheDigitsOfHarshadNumber(100) == 1     # Upper constraint boundary

assert solution.sumOfTheDigitsOfHarshadNumber(21) == 3      # Another valid Harshad number
assert solution.sumOfTheDigitsOfHarshadNumber(19) == -1     # Prime non-Harshad number

Test Summary

Test	Why
`18`	Basic valid Harshad number
`23`	Basic invalid Harshad number
`1`	Minimum constraint value
`9`	Single digit divisibility
`10`	Number containing zero
`12`	Standard divisible case
`11`	Standard non-divisible case
`99`	Larger digit sum
`100`	Maximum constraint value
`21`	Another divisible example
`19`	Prime number that fails divisibility

Edge Cases

Single Digit Numbers

Single digit numbers are important because their digit sum equals the number itself. For example, 7 has digit sum 7, and 7 % 7 == 0.

A buggy implementation might accidentally mishandle small inputs or terminate the loop incorrectly. Our implementation handles this naturally because the loop processes the single digit once and computes the correct sum.

Numbers Containing Zero

Inputs like 10 or 100 contain zeros, which sometimes expose digit extraction bugs.

For 100, the digit sum is:

1 + 0 + 0 = 1

Our arithmetic approach correctly processes zero digits because x % 10 returns 0 for those positions, and adding zero does not affect the sum.

Non-Harshad Numbers

Numbers like 23 or 19 are not divisible by their digit sums.

Some incorrect solutions accidentally return the digit sum regardless of divisibility. Our implementation explicitly checks:

if original % digit_sum == 0:

and returns -1 otherwise, ensuring invalid numbers are handled correctly.