Check if a Number is a Harshad (Niven) Number

37
0

Given a positive integer N, call it a Harshad (Niven) number if the sum of its decimal digits divides it evenly.

Return true if N is a Harshad number and false otherwise.

Example 1

Input: N = 2016

Output: true

Explanation: The digit sum is 2 + 0 + 1 + 6 = 9. Dividing 2016 by 9 leaves a remainder of 0.

Example 2

Input: N = 19

Output: false

Explanation: The digit sum is 1 + 9 = 10. Dividing 19 by 10 leaves a remainder of 9.

Approach

The number must be divisible by its digit sum, so the main task is to find that sum. In decimal notation, every digit except the last contributes a multiple of 10. Dividing by 10 therefore gives the last digit as the remainder. The quotient without its decimal part gives the remaining digits.

The same idea applies to the remaining number. Repeating this separation reveals each digit exactly once, so adding those digits gives the required sum.

Removing digits eventually reduces the working number to 0. A working copy keeps the original N available for the final divisibility check. If dividing N by the digit sum leaves a remainder of 0, N is a Harshad number.

Algorithm

  • Keep the original N for the divisibility check and make a working copy.

  • Start the digit sum at 0.

  • While the copy is positive, find its last digit using the remainder after division by 10 and add that digit to the sum.

  • Remove the last digit using integer division by 10. The scan ends when the copy reaches 0, which takes one step for any single-digit input.

  • Return whether dividing the original N by the digit sum leaves a remainder of 0.

Dry Run

Check if a Number is a Harshad (Niven) Number

Check if a Number is a Harshad (Niven) Number

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns whether N is divisible by its decimal digit sum.
bool isHarshad(long long N) {
long long remaining = N;
long long digitSum = 0;
// Add the last digit and remove it from the working copy.
while (remaining > 0) {
digitSum += remaining % 10;
remaining /= 10;
}
return N % digitSum == 0;
}
};
// Driver code
int main() {
long long N = 2016;
// instance for class Solution
Solution sol;
cout << boolalpha << sol.isHarshad(N) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(D), where D is the number of decimal digits in N.

Space Complexity: O(1) auxiliary space because the working copy and digit sum occupy a fixed number of variables for the stated input range.

Interview follow-up Questions

Yes. Its only digit equals the number itself, and every positive integer is divisible by itself.

MathsTCS NQT

Read Similar Blogs

Comments0