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.
This is a more efficient approach that uses mathematical operations to extract and sum the digits, avoiding the overhead of string conversion. We repeatedly take the number modulo 10 to get the last digit and then divide the number by 10 to remove the last digit, continuing this process until the number becomes zero.
Algorithm
- Create a copy of the input integer
xto preserve its original value, let's call itcurrentNumber. - Initialize a variable
sumOfDigitsto 0. - Start a loop that continues as long as
currentNumberis greater than 0. - Inside the loop, calculate the last digit using the modulo operator:
digit = currentNumber % 10. - Add the
digittosumOfDigits. - Update
currentNumberby performing integer division by 10 to remove the last digit:currentNumber = currentNumber / 10. - After the loop, check if the original number
xis divisible bysumOfDigits. - If
x % sumOfDigits == 0, returnsumOfDigits. - Otherwise, return -1.
Walkthrough
This method relies on pure arithmetic to calculate the sum of digits. The modulo operator (%) is used to get the last digit of a number (e.g., 18 % 10 = 8), and integer division (/) is used to remove the last digit (e.g., 18 / 10 = 1). We repeat this process in a loop until the number is reduced to 0, summing up the digits we extract along the way. This avoids creating any new objects and is generally faster and more memory-efficient.
For example, if x = 18:
- Initialize
sumOfDigits = 0,temp = 18. - Loop 1:
temp > 0(18 > 0).sumOfDigits += 18 % 10(sum becomes 8).temp = 18 / 10(temp becomes 1). - Loop 2:
temp > 0(1 > 0).sumOfDigits += 1 % 10(sum becomes 8 + 1 = 9).temp = 1 / 10(temp becomes 0). - Loop 3:
temp > 0(0 > 0) is false. The loop terminates. - The sum is
9. - Check if
18 % 9 == 0. It is true. - Return the sum,
9.
class Solution { public int sumOfTheDigitsOfHarshadNumber(int x) { int sumOfDigits = 0; int temp = x; while (temp > 0) { sumOfDigits += temp % 10; temp /= 10; } if (x % sumOfDigits == 0) { return sumOfDigits; } else { return -1; } }}Complexity
Time
O(log10(x)) - The number of iterations in the while loop is equal to the number of digits in `x`. The number of digits is logarithmically related to the value of `x`.
Space
O(1) - This approach uses a fixed number of variables (`sumOfDigits`, `temp`) regardless of the size of the input integer `x`. No dynamic memory allocation that scales with the input size is needed.
Trade-offs
Pros
Highly efficient in terms of space, using only a constant amount of extra memory (O(1)).
Generally faster in practice as it avoids the overhead of type conversions and string object creation.
Works with fundamental arithmetic operations, which is a core programming skill.
Cons
Might be slightly less intuitive for complete beginners compared to the string manipulation approach.
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; }}class Solution: def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int: s, y = 0, x while y: s += y % 10 y //= 10 return s if x % s == 0 else - 1class 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.