LeetCode 3099: Harshad Number (Digit Sum + Divisibility Check)

2026-04-13 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 3099MathDigit Sum

Today we solve LeetCode 3099 - Harshad Number.

Source: https://leetcode.com/problems/harshad-number/

LeetCode 3099 digit-sum divisibility diagram

English

Problem Summary

Given a positive integer x, compute the sum of its digits. If x is divisible by that digit sum, return the digit sum; otherwise return -1.

Key Insight

This is a direct math check: first extract digits to get sum, then test x % sum == 0. Because x > 0, sum is always positive and safe for modulo.

Algorithm

1) Save original value n = x.
2) Repeatedly take last digit n % 10 and add to sum.
3) Remove last digit by n /= 10 until n == 0.
4) If x % sum == 0, return sum; else return -1.

Complexity Analysis

If x has d digits, we loop d times.
Time: O(d) = O(log10 x).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int n = x;
        int sum = 0;

        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }

        return x % sum == 0 ? sum : -1;
    }
}

func sumOfTheDigitsOfHarshadNumber(x int) int {
    n := x
    sum := 0

    for n > 0 {
        sum += n % 10
        n /= 10
    }

    if x%sum == 0 {
        return sum
    }
    return -1
}

class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int n = x;
        int sum = 0;

        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }

        return (x % sum == 0) ? sum : -1;
    }
};

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        n = x
        s = 0

        while n > 0:
            s += n % 10
            n //= 10

        return s if x % s == 0 else -1

var sumOfTheDigitsOfHarshadNumber = function(x) {
  let n = x;
  let sum = 0;

  while (n > 0) {
    sum += n % 10;
    n = Math.floor(n / 10);
  }

  return x % sum === 0 ? sum : -1;
};

中文

题目概述

给定一个正整数 x，先计算它的各位数字之和。如果 x 能被这个和整除，返回该和；否则返回 -1。

核心思路

本题就是“拆位 + 整除判断”。先把各位数字累加得到 sum，再判断 x % sum == 0 即可。由于 x > 0，所以 sum 一定大于 0。

算法步骤

1）保存原值 n = x。
2）循环取末位 n % 10 加到 sum。
3）用 n /= 10（或整除）去掉末位，直到 n == 0。
4）若 x % sum == 0 返回 sum，否则返回 -1。

复杂度分析

设 x 有 d 位，需要遍历每一位一次。
时间复杂度：O(d)，即 O(log10 x)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int n = x;
        int sum = 0;

        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }

        return x % sum == 0 ? sum : -1;
    }
}

func sumOfTheDigitsOfHarshadNumber(x int) int {
    n := x
    sum := 0

    for n > 0 {
        sum += n % 10
        n /= 10
    }

    if x%sum == 0 {
        return sum
    }
    return -1
}

class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int n = x;
        int sum = 0;

        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }

        return (x % sum == 0) ? sum : -1;
    }
};

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        n = x
        s = 0

        while n > 0:
            s += n % 10
            n //= 10

        return s if x % s == 0 else -1

var sumOfTheDigitsOfHarshadNumber = function(x) {
  let n = x;
  let sum = 0;

  while (n > 0) {
    sum += n % 10;
    n = Math.floor(n / 10);
  }

  return x % sum === 0 ? sum : -1;
};