Skip to main content
Talentd

Harshad Number - Solution & Explanation

EasyMath12 min readAsked at: Microsoft
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: A Harshad number (or Niven number) is an integer that is divisible by the sum of its digits. Given an integer x, compute the sum of its digits and check whether x % digitSum == 0. If it is divisible, return the digit sum; otherwise return -1. The task mainly tests basic number manipulation and math fundamentals.

Approach 1: Digit Sum Calculation and Modulo Check (O(d) time, O(1) space)

This is the straightforward and optimal method. Iterate through the digits of the number by repeatedly taking x % 10 to extract the last digit and adding it to a running sum. After extracting a digit, remove it using integer division x /= 10. Once all digits are processed, check if the original number is divisible by the computed digit sum using a modulo operation. If original % sum == 0, the number is a Harshad number and the digit sum is returned; otherwise return -1. The algorithm processes each digit once, so the time complexity is O(d) where d is the number of digits (equivalently O(log10 n)). Space usage stays O(1) since only a few integer variables are used.

Approach 2: Recursive Digit Sum and Check (O(d) time, O(d) space)

This approach computes the digit sum using recursion instead of an iterative loop. Define a recursive function that returns 0 when the number becomes 0. For each call, add n % 10 to the result of the recursive call on n / 10. Once the digit sum is computed, perform the same divisibility check as before: x % digitSum == 0. The recursion depth equals the number of digits, giving O(d) time and O(d) auxiliary stack space. This version is useful for practicing recursion, though it offers no performance advantage over the iterative method.

Recommended for interviews: The iterative digit-sum approach is what interviewers expect. It demonstrates that you understand basic digit extraction using division and modulo operations, a common pattern in math problems. The recursive solution is valid but usually unnecessary; interviewers typically prefer the constant-space iterative implementation.

Approach 1: Digit Sum Calculation and Modulo Check

This approach involves calculating the sum of digits of the integer x and checking if x is divisible by this sum. If it is, x is a Harshad number, and we return the sum of its digits; otherwise, we return -1.

The solution defines a function to calculate the sum of digits for the given number. Then, it uses a modulo operation to determine if the number is divisible by the sum of its digits, returning the sum if true and -1 otherwise.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(x)), where x is the given number. This is due to the digit extraction process.
Space Complexity: O(1), as minimal extra space is used.

Try this approach in the editor →

Approach 2: Recursive Digit Sum and Check

This approach uses a recursive function to calculate the sum of the digits and then checks whether x is divisible by this sum. It offers an alternative way to calculate the sum of digits using recursion, which can be easier to understand or fit with different recursion-based strategies.

This approach uses a recursive function to process each digit, adding it to the total. The harshadNumberCheck function verifies divisibility in the same way.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(x)), largely due to recursion depth per digit.
Space Complexity: O(log(x)), due to recursion stack size.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(log x), where x is the input integer. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Digit Sum Calculation and Modulo Check

Time Complexity: O(log(x)), where x is the given number. This is due to the digit extraction process.
Space Complexity: O(1), as minimal extra space is used.

Recursive Digit Sum and Check

Time Complexity: O(log(x)), largely due to recursion depth per digit.
Space Complexity: O(log(x)), due to recursion stack size.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Digit Sum Calculation and Modulo CheckO(d)O(1)General case; simplest and most efficient implementation
Recursive Digit Sum and CheckO(d)O(d)When practicing recursion or learning digit decomposition

Video Solution

3099. Harshad Number (Leetcode Easy) • Programming Live with Larry • 295 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Harshad Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer