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
Nfor 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
10and add that digit to the sum.Remove the last digit using integer division by
10. The scan ends when the copy reaches0, which takes one step for any single-digit input.Return whether dividing the original
Nby the digit sum leaves a remainder of0.
Dry Run
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 codeint 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.
Be the first to add a comment.