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.
Example 1:
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 and the answer is 9.
Example 2:
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 and the answer is -1.
Constraints:
1 <= x <= 100Problem Overview: A Harshad number (or Niven number) is an integer that is divisible by the sum of its digits. Given an integer x, compute the sum of its digits and check whether x % digitSum == 0. If it is divisible, return the digit sum; otherwise return -1. The task mainly tests basic number manipulation and math fundamentals.
Approach 1: Digit Sum Calculation and Modulo Check (O(d) time, O(1) space)
This is the straightforward and optimal method. Iterate through the digits of the number by repeatedly taking x % 10 to extract the last digit and adding it to a running sum. After extracting a digit, remove it using integer division x /= 10. Once all digits are processed, check if the original number is divisible by the computed digit sum using a modulo operation. If original % sum == 0, the number is a Harshad number and the digit sum is returned; otherwise return -1. The algorithm processes each digit once, so the time complexity is O(d) where d is the number of digits (equivalently O(log10 n)). Space usage stays O(1) since only a few integer variables are used.
Approach 2: Recursive Digit Sum and Check (O(d) time, O(d) space)
This approach computes the digit sum using recursion instead of an iterative loop. Define a recursive function that returns 0 when the number becomes 0. For each call, add n % 10 to the result of the recursive call on n / 10. Once the digit sum is computed, perform the same divisibility check as before: x % digitSum == 0. The recursion depth equals the number of digits, giving O(d) time and O(d) auxiliary stack space. This version is useful for practicing recursion, though it offers no performance advantage over the iterative method.
Recommended for interviews: The iterative digit-sum approach is what interviewers expect. It demonstrates that you understand basic digit extraction using division and modulo operations, a common pattern in math problems. The recursive solution is valid but usually unnecessary; interviewers typically prefer the constant-space iterative implementation.
This approach involves calculating the sum of digits of the integer x and checking if x is divisible by this sum. If it is, x is a Harshad number, and we return the sum of its digits; otherwise, we return -1.
The solution defines a function to calculate the sum of digits for the given number. Then, it uses a modulo operation to determine if the number is divisible by the sum of its digits, returning the sum if true and -1 otherwise.
Time Complexity: O(log(x)), where x is the given number. This is due to the digit extraction process.
Space Complexity: O(1), as minimal extra space is used.
This approach uses a recursive function to calculate the sum of the digits and then checks whether x is divisible by this sum. It offers an alternative way to calculate the sum of digits using recursion, which can be easier to understand or fit with different recursion-based strategies.
This approach uses a recursive function to process each digit, adding it to the total. The harshadNumberCheck function verifies divisibility in the same way.
Time Complexity: O(log(x)), largely due to recursion depth per digit.
Space Complexity: O(log(x)), due to recursion stack size.
We can calculate the sum of the digits of x, denoted as s, by simulation. If x can be divided evenly by s, then we return s, otherwise, we return -1.
The time complexity is O(log x), where x is the input integer. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Digit Sum Calculation and Modulo Check | Time Complexity: O(log(x)), where x is the given number. This is due to the digit extraction process. |
| Recursive Digit Sum and Check | Time Complexity: O(log(x)), largely due to recursion depth per digit. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Digit Sum Calculation and Modulo Check | O(d) | O(1) | General case; simplest and most efficient implementation |
| Recursive Digit Sum and Check | O(d) | O(d) | When practicing recursion or learning digit decomposition |
LeetCode#3099 Harshad Number - Python • CodeJulian • 597 views views
Watch 9 more video solutions →Practice Harshad Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor