How do you solve Harshad Number on LeetCode?

Harshad Number (LeetCode #3099) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: A Harshad number is defined by its divisibility by the sum of its digits.

What is the brute force solution for Harshad Number?

The brute force approach for Harshad Number is Brute Force, with O(n) time complexity and O(1) space complexity. To determine if a number is a Harshad number, we can calculate the sum of its digits and check if the number is divisible by this sum. This approach is straightforward and easy to understand. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Harshad Number?

Harshad Number uses the following concepts: Math. The recommended patterns to study are: Math, Looping through digits.

What are the interview tips for Harshad Number?

Clarify the problem statement before diving into coding. Discuss your thought process while coding to show your understanding. Test your code with edge cases to ensure robustness.

What are common mistakes when solving Harshad Number?

Forgetting to reset the original number after calculating the sum of digits. Not handling the case when the sum of digits is zero (though it won't happen with given constraints).

#3099

Harshad Number

Easy

MathMathLooping through digits

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution is essentially the same as the brute force approach, but we can clarify our understanding of the problem and ensure that we handle edge cases effectively. The logic remains linear, but we ensure clarity in our implementation.

⚙️

Algorithm

3 steps

1Step 1: Initialize a variable to hold the sum of digits.
2Step 2: Use a while loop to extract each digit of the number by taking the modulus with 10 and adding it to the sum.
3Step 3: After the loop, check if the original number is divisible by the sum of its digits. If yes, return the sum; otherwise, return -1.

solution.py9 lines

1# Full working Python code
2
3def is_harshad_number(x):
4    sum_of_digits = 0
5    original = x
6    while x > 0:
7        sum_of_digits += x % 10
8        x //= 10
9    return sum_of_digits if original % sum_of_digits == 0 else -1

ℹ

Complexity note: The time complexity is O(n) because we iterate through each digit of the number. The space complexity is O(1) since we only use a fixed amount of extra space.

1A Harshad number is defined by its divisibility by the sum of its digits.
2The sum of digits can be calculated using a simple loop.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.