Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Harshad Number solution and explanation

EasyMath4 min read83.4% acceptanceUpdated 9 Apr 2026
Asked atMicrosoft
Practise Harshad Number
2:57
3099. Harshad Number (Leetcode Easy)Programming Live with Larry · 2:57 · 295 viewsWatch on YouTube
9 more videos on this problem
  1. 3099. Harshad Number (Leetcode Easy)Programming Live with Larry · 2:57 · 295 views
  2. Leetcode 3099 Harshad NumberTech Diet · 1:33 · 276 views
  3. Leetcode Weekly 391: Harshad Number | Ranked 114 - Brute Force to OptimisationsBharat Khanna · 5:34 · 241 views
  4. 3099. Harshad Number | LEETCODE EASYcode Explainer · 2:18 · 168 views
  5. 3099. Harshad Number | Find Sum of digitsTech Courses · 2:37 · 162 views
  6. 🔢 Harshad Number Solution in C++ | LeetCode Problem 3099Raj Kumar Mahto · 1:38 · 77 views
  7. my attempt at solving leetcode 3099: harshad number [SOLVED]Cameron Late · 4:04 · 43 views
  8. Leetcode easy problem 3099. Harshad Number | devops python practiceADevOpsEngineer · 1:13 · 41 views
  9. Rust LeetCode 3099 Harshad Number NarrationTheShortBlueDragon · 1:36 · 36 views
  10. Harshad Number - Leetcode 3099 || Weekly Contest 391 || Easy || Maths || Digit sumLevel up with Coding · 10:17 · 35 views

The 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.

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.

def sum_of_digits(x):
    return sum(int(d) for d in str(x))

def harshad_number_check(x):
    digit_sum = sum_of_digits(x)
    return digit_sum if x % digit_sum == 0 else -1

x = 23
print(harshad_number_check(x))
public class HarshadNumber {
    public static int sumOfDigits(int x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }

    public static int harshadNumberCheck(int x) {
        int digitSum = sumOfDigits(x);
        return (x % digitSum == 0) ? digitSum : -1;
    }

    public static void main(String[] args) {
        int x = 18;
        System.out.println(harshadNumberCheck(x));
    }
}
#include <iostream>

int sumOfDigits(int x) {
    int sum = 0;
    while (x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int harshadNumberCheck(int x) {
    int digitSum = sumOfDigits(x);
    return (x % digitSum == 0) ? digitSum : -1;
}

int main() {
    int x = 23;
    std::cout << harshadNumberCheck(x) << std::endl;
    return 0;
}
function sumOfDigits(x) {
    return x.toString().split('').reduce((sum, digit) => sum + parseInt(digit), 0);
}

function harshadNumberCheck(x) {
    const digitSum = sumOfDigits(x);
    return (x % digitSum === 0) ? digitSum : -1;
}

let x = 18;
console.log(harshadNumberCheck(x));
#include <stdio.h>

int sumOfDigits(int x) {
    int sum = 0;
    while (x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int harshadNumberCheck(int x) {
    int digitSum = sumOfDigits(x);
    return (x % digitSum == 0) ? digitSum : -1;
}

int main() {
    int x = 18;
    printf("%d\n", harshadNumberCheck(x));
    return 0;
}
using System;

public class HarshadNumber {
    public static int SumOfDigits(int x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }

    public static int HarshadNumberCheck(int x) {
        int digitSum = SumOfDigits(x);
        return (x % digitSum == 0) ? digitSum : -1;
    }

    public static void Main() {
        int x = 18;
        Console.WriteLine(HarshadNumberCheck(x));
    }
}

This Python solution leverages list comprehension to sum the digits quickly before performing the modulo operation for the Harshad number check.

Complexity

Time Complexity: O(log(x)), due to iterating over digits.
Space Complexity: O(1).

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.

def sum_of_digits(x):
    if x == 0:
        return 0
    return x % 10 + sum_of_digits(x // 10)

def harshad_number_check(x):
    digit_sum = sum_of_digits(x)
    return digit_sum if x % digit_sum == 0 else -1

x = 23
print(harshad_number_check(x))
public class HarshadNumber {
    public static int sumOfDigits(int x) {
        if (x == 0) return 0;
        return (x % 10) + sumOfDigits(x / 10);
    }

    public static int harshadNumberCheck(int x) {
        int digitSum = sumOfDigits(x);
        return (x % digitSum == 0) ? digitSum : -1;
    }

    public static void main(String[] args) {
        int x = 18;
        System.out.println(harshadNumberCheck(x));
    }
}
#include <iostream>

int sumOfDigits(int x) {
    if (x < 10) return x;
    return x % 10 + sumOfDigits(x / 10);
}

int harshadNumberCheck(int x) {
    int digitSum = sumOfDigits(x);
    return (x % digitSum == 0) ? digitSum : -1;
}

int main() {
    int x = 23;
    std::cout << harshadNumberCheck(x) << std::endl;
    return 0;
}
function sumOfDigits(x) {
    if (x === 0) return 0;
    return x % 10 + sumOfDigits(Math.floor(x / 10));
}

function harshadNumberCheck(x) {
    const digitSum = sumOfDigits(x);
    return (x % digitSum === 0) ? digitSum : -1;
}

let x = 23;
console.log(harshadNumberCheck(x));
#include <stdio.h>

int sumOfDigits(int x) {
    if (x == 0) return 0;
    return x % 10 + sumOfDigits(x / 10);
}

int harshadNumberCheck(int x) {
    int digitSum = sumOfDigits(x);
    return (x % digitSum == 0) ? digitSum : -1;
}

int main() {
    int x = 23;
    printf("%d\n", harshadNumberCheck(x));
    return 0;
}
using System;

public class HarshadNumber {
    public static int SumOfDigits(int x) {
        if (x == 0) return 0;
        return (x % 10) + SumOfDigits(x / 10);
    }

    public static int HarshadNumberCheck(int x) {
        int digitSum = SumOfDigits(x);
        return (x % digitSum == 0) ? digitSum : -1;
    }

    public static void Main() {
        int x = 18;
        Console.WriteLine(HarshadNumberCheck(x));
    }
}

Simple recursion calculates digit sums in Python, while subsequent steps determine Harshad number status using straightforward modulo logic.

Complexity

Time Complexity: O(log(x)).
Space Complexity: O(log(x)).

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).

function sumOfTheDigitsOfHarshadNumber(x: number): number {
    let s = 0;
    for (let y = x; y; y = Math.floor(y / 10)) {
        s += y % 10;
    }
    return x % s === 0 ? s : -1;
}
func sumOfTheDigitsOfHarshadNumber(x int) int {
	s := 0
	for y := x; y > 0; y /= 10 {
		s += y % 10
	}
	if x%s == 0 {
		return s
	}
	return -1
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Digit Sum Calculation and Modulo Check

Time Complexity: O(log(x)), due to iterating over digits.
Space Complexity: O(1).

Recursive Digit Sum and Check

Time Complexity: O(log(x)).
Space Complexity: O(log(x)).

Simulation–

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

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.

Comments

Now write it yourselfClose this page and solve Harshad Number in the editor, without looking.
Practise Harshad Number