#3099

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Harshad Number

Given an integer, determine if it is a Harshad number by checking if it's divisible by the sum of its digits.

Problem Statement

Given an integer x, determine if it is a Harshad number. A Harshad number is an integer divisible by the sum of its digits. You need to return the sum of the digits of x if it is a Harshad number, or return -1 if it is not.

For example, if x = 18, the sum of digits is 9, and since 18 is divisible by 9, it is a Harshad number, so the answer would be 9. If x = 23, the sum of digits is 5, and since 23 is not divisible by 5, it is not a Harshad number, and the answer is -1.

Examples

Example 1

Input: x = 18

Output: 9

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

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 Approach

Sum the digits of the number

Start by extracting the sum of digits of the number x using a simple while loop that repeatedly divides x by 10.

Check divisibility

Once the sum of the digits is computed, check if the original number x is divisible by this sum. If it is divisible, return the sum, otherwise return -1.

Efficient calculation

The solution can be computed in constant time for small integers like the one provided in the constraints (1 <= x <= 100). Therefore, a simple iteration over the digits of x is efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(d) where d is the number of digits in x (which will be small given the constraints). The space complexity is O(1) as no additional space is used apart from a few variables.

What Interviewers Usually Probe

Looking for understanding of basic math operations and modular arithmetic.
Should be able to identify the simple approach of summing digits.
Test if candidate can efficiently implement digit extraction and divisibility check.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the case where the sum of digits does not divide x properly.
Using a string-based approach for digit extraction instead of mathematical operations.
Confusing the sum of digits with the actual number itself and not performing the divisibility check correctly.

Follow-up variants

Try the problem for larger numbers to test efficiency.
Modify the problem to check if a number is divisible by the product of its digits instead of the sum.
Consider edge cases like very small numbers or numbers with repeating digits.

FAQ

What is a Harshad number?

A Harshad number is an integer that is divisible by the sum of its digits.

How do I calculate the sum of digits of a number?

You can calculate the sum of digits by repeatedly dividing the number by 10 and adding the remainders.

What if the number is not divisible by the sum of its digits?

If the number is not divisible by the sum of its digits, the correct output is -1.

How is this problem solved efficiently?

This problem is solved efficiently by using basic math operations like digit extraction and divisibility check, which work in constant time for small integers.

Can I solve this problem using a string approach?

While a string approach is possible, using mathematical operations like dividing by 10 is more efficient and aligns better with the problem's pattern.

terminal

Solution

Solution 1: Simulation

We can calculate the sum of the digits of $x$, denoted as $s$, by simulation. If $x$ can be divided evenly by $s$, then we return $s$, otherwise, we return $-1$.

1

2

3

4

5

6

7

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

Continue Practicing

#3100 water bottles ii #3101 count alternating subarrays #3102 minimize manhattan distances