# Harshad Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/harshad-number)
Canonical: https://scaleengineer.com/dsa/problems/harshad-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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
## String Conversion and Iteration
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.
**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`.
**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.
### Explanation
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`:
1. Convert `18` to the string `"18"`.
2. Initialize `sumOfDigits = 0`.
3. First character is '1'. Convert '1' to `1`. `sumOfDigits` becomes `0 + 1 = 1`.
4. Second character is '8'. Convert '8' to `8`. `sumOfDigits` becomes `1 + 8 = 9`.
5. The loop ends. The sum is `9`.
6. Check if `18 % 9 == 0`. It is true.
7. Return the sum, `9`.

```java
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;
        }
    }
}
```
### Algorithm
- Convert the input integer `x` to its string representation, let's call it `s`.
- Initialize a variable `sumOfDigits` to 0.
- Iterate through each character `c` in the string `s`.
- 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, `sumOfDigits` will hold the sum of all digits of `x`.
- Check if the original number `x` is divisible by `sumOfDigits` using the modulo operator (`x % sumOfDigits == 0`).
- If it is divisible, return `sumOfDigits`.
- Otherwise, return -1.

## Iterative Calculation using Modulo Arithmetic
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.
**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.
**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.
### Explanation
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`:
1. Initialize `sumOfDigits = 0`, `temp = 18`.
2. **Loop 1:** `temp > 0` (18 > 0). `sumOfDigits += 18 % 10` (sum becomes 8). `temp = 18 / 10` (temp becomes 1).
3. **Loop 2:** `temp > 0` (1 > 0). `sumOfDigits += 1 % 10` (sum becomes 8 + 1 = 9). `temp = 1 / 10` (temp becomes 0).
4. **Loop 3:** `temp > 0` (0 > 0) is false. The loop terminates.
5. The sum is `9`.
6. Check if `18 % 9 == 0`. It is true.
7. Return the sum, `9`.

```java
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;
        }
    }
}
```
### Algorithm
- Create a copy of the input integer `x` to preserve its original value, let's call it `currentNumber`.
- Initialize a variable `sumOfDigits` to 0.
- Start a loop that continues as long as `currentNumber` is greater than 0.
- Inside the loop, calculate the last digit using the modulo operator: `digit = currentNumber % 10`.
- Add the `digit` to `sumOfDigits`.
- Update `currentNumber` by performing integer division by 10 to remove the last digit: `currentNumber = currentNumber / 10`.
- After the loop, check if the original number `x` is divisible by `sumOfDigits`.
- If `x % sumOfDigits == 0`, return `sumOfDigits`.
- Otherwise, return -1.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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 - 1

```

### CPP

```cpp
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;
  }
};

```