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 .

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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

Solution

Method 1 – Digit Sum Check

Intuition

A Harshad number is divisible by the sum of its digits. We simply compute the digit sum and check divisibility.

Approach

  1. Compute the sum of digits of x.
  2. If x is divisible by the digit sum, return the digit sum.
  3. Otherwise, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int s = 0, t = x;
        while (t) {
            s += t % 10;
            t /= 10;
        }
        return x % s == 0 ? s : -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func sumOfTheDigitsOfHarshadNumber(x int) int {
    s, t := 0, x
    for t > 0 {
        s += t % 10
        t /= 10
    }
    if x%s == 0 {
        return s
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int s = 0, t = x;
        while (t > 0) {
            s += t % 10;
            t /= 10;
        }
        return x % s == 0 ? s : -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun sumOfTheDigitsOfHarshadNumber(x: Int): Int {
        var s = 0
        var t = x
        while (t > 0) {
            s += t % 10
            t /= 10
        }
        return if (x % s == 0) s else -1
    }
}
1
2
3
4

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        s = sum(int(d) for d in str(x))
        return s if x % s == 0 else -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct Solution;
impl Solution {
    pub fn sum_of_the_digits_of_harshad_number(x: i32) -> i32 {
        let mut s = 0;
        let mut t = x;
        while t > 0 {
            s += t % 10;
            t /= 10;
        }
        if x % s == 0 { s } else { -1 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    sumOfTheDigitsOfHarshadNumber(x: number): number {
        let s = 0, t = x;
        while (t > 0) {
            s += t % 10;
            t = Math.floor(t / 10);
        }
        return x % s === 0 ? s : -1;
    }
}

Complexity

  • ⏰ Time complexity: O(log x), since we process each digit of x.
  • 🧺 Space complexity: O(1), only a few variables are used.