Watch 10 video solutions for Harshad Number, a easy level problem involving Math. This walkthrough by CodeJulian has 597 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |