Harshad Number
EasyPrompt
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 <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves converting the integer to its string representation to easily access each digit. We then iterate through the characters of the string, convert each character back to a numeric value, and sum them up. Finally, we check if the original number is divisible by this sum.
Algorithm
- Convert the input integer
xto its string representation, let's call its. - Initialize a variable
sumOfDigitsto 0. - Iterate through each character
cin the strings. - For each character, convert it to its integer equivalent (e.g., by subtracting the ASCII value of '0') and add it to
sumOfDigits. - After the loop finishes,
sumOfDigitswill hold the sum of all digits ofx. - Check if the original number
xis divisible bysumOfDigitsusing the modulo operator (x % sumOfDigits == 0). - If it is divisible, return
sumOfDigits. - Otherwise, return -1.
Walkthrough
The core idea is to leverage built-in string conversion functionalities. By converting the number x into a string, we can treat it as a sequence of characters. We can then loop through these characters, convert each one back into a number, and accumulate the sum. This method is often straightforward to write and understand.
For example, if x = 18:
- Convert
18to the string"18". - Initialize
sumOfDigits = 0. - First character is '1'. Convert '1' to
1.sumOfDigitsbecomes0 + 1 = 1. - Second character is '8'. Convert '8' to
8.sumOfDigitsbecomes1 + 8 = 9. - The loop ends. The sum is
9. - Check if
18 % 9 == 0. It is true. - Return the sum,
9.
class Solution { public int sumOfTheDigitsOfHarshadNumber(int x) { String s = Integer.toString(x); int sumOfDigits = 0; for (char c : s.toCharArray()) { sumOfDigits += c - '0'; // Convert character to its integer value } if (x % sumOfDigits == 0) { return sumOfDigits; } else { return -1; } }}Complexity
Time
O(log10(x)) - The time taken is proportional to the number of digits in `x`. Converting an integer to a string and then iterating over that string both take time linear to the number of digits.
Space
O(log10(x)) - Additional space is required to store the string representation of the number `x`. The length of this string is proportional to the number of digits in `x`.
Trade-offs
Pros
Conceptually simple and easy to read, especially for those familiar with string manipulation.
The code can be very concise.
Cons
Less efficient in terms of space complexity as it requires creating a new string object to hold the digits.
Involves type conversions (integer to string, character to integer) which can introduce a slight performance overhead compared to pure arithmetic operations.
Solutions
Solution
class Solution {public int sumOfTheDigitsOfHarshadNumber(int x) { int s = 0; for (int y = x; y > 0; y /= 10) { s += y % 10; } return x % s == 0 ? s : -1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.