Is Harshad Number easy or hard?

Harshad Number is classified as an Easy problem. It mainly checks understanding of digit manipulation, modulo arithmetic, and simple control flow. Most implementations are under 10 lines of code.

Harshad Number Python/Java solution

In Python or Java, compute the digit sum using a loop that repeatedly extracts digits with %10 and divides the number by 10. After computing the sum, check if the original value modulo the digit sum equals zero. If divisible, return the digit sum; otherwise return -1.

How to solve Harshad Number in O(n)?

Treat n as the number of digits and iterate through each digit once. Compute the digit sum using modulo and division operations, then check if the original number is divisible by that sum. This results in O(d) time complexity and constant extra space.

What is the best approach for Harshad Number?

The best approach is computing the digit sum and checking divisibility using a modulo operation. Extract digits with repeated %10 and divide the number by 10 until it becomes zero. This runs in O(d) time where d is the number of digits and uses O(1) extra space.

Is Harshad Number asked at Google/Amazon/Meta?

Harshad Number itself is usually categorized as an easy math problem, but the digit extraction pattern frequently appears in interviews at companies like Amazon and Google. Variations include digit sum constraints, palindrome numbers, and other number manipulation tasks.

What data structure is used in Harshad Number?

No specialized data structure is required. The solution relies on simple arithmetic operations such as modulo (%) and integer division to process digits. Only a few integer variables are needed to store the running digit sum and the original number.

What is the time complexity of Harshad Number?

The time complexity is O(d), where d represents the number of digits in the input number. Since d is proportional to log10(n), the algorithm effectively runs in O(log n) relative to the numeric value. Only a single pass over the digits is required.

Description Hints 1 Solution Video 2:57

3099. Harshad Number

Easy83.4% acceptance1 company

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

Asked at 1 company

Microsoft

Topics

Math

Hints open one at a time

Hint 1

Use a while loop and divide x by 10 to find the sum of the digits of x.

2:57

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution