Definition
n % s(n) = 0
Positive n is Harshad if it is divisible by the sum of its decimal digits.
Check Harshad Number in C
Overview
What You’ll Learn
Harshad numbers are a classic interview warm-up: digit extraction plus one divisibility test. This tutorial covers the base-10 definition, a safe C helper that avoids % 0, a live preview, algorithm steps, worked C examples, edge cases, and complexity.
Digit Sum
% 10 loop
Peel digits with n % 10, accumulate, divide by 10.
Zero Guard
No % 0
Reject n ≤ 0 so the digit sum is never used as a zero divisor.
Range Scan
1–20
List every Harshad value in a closed interval with the same helper.
Live Preview
Check n
See digit sum, remainder, and Harshad / not Harshad instantly.
Niven Alias
Same class
Also called Niven numbers — same base-10 digit-sum rule.
Introduction
A Harshad number (also called a Niven number) is a positive integer n that is divisible by the sum of its decimal digits. For 18, digits sum to 9, and 18 % 9 == 0, so 18 is Harshad.
In C interviews you are usually asked to implement a digit-sum helper, test original % sum == 0, guard against n ≤ 0, and optionally list Harshad numbers in a range.
Why it matters?
It trains digit loops, divisibility, and careful zero guards — skills that show up in many digit-property problems (digital roots, checksums, other bases).
Key Highlights
s(n) Divides n
One digit sum, one modulus test.
Keep Original
Digit loop destroys n — save a copy first.
Single Digits Pass
For 1..9, s(n) = n, so all are Harshad.
Never % 0
Reject non-positive n before dividing.
In short: for positive n, compute the sum of decimal digits s, then check n % s == 0 — that is the Harshad test.
Foundation
📝 Problem & Approach
Given a positive integer n, decide whether it is Harshad in base 10; optionally list every Harshad value in a closed interval.
c
/* n = 18
* digits: 1 + 8 = 9
* 18 % 9 == 0 → Harshad
*
* n = 11
* digits: 1 + 1 = 2
* 11 % 2 != 0 → not Harshad
*/Inputs & Outputs
| Item | Type | Description |
|---|---|---|
n / number | int | Positive integer to classify (Example 1). |
| Range bounds | int | Inclusive interval such as [1, 20] (Example 2). |
| Result | flag / text | Harshad or not; or a printed list of Harshad values. |
Minimal workflow
Pseudocode
function digit_sum_base10(n): // assume n >= 0
s = 0
while n > 0:
s += (n mod 10)
n = floor(n / 10)
return s
function is_harshad(n):
if n <= 0:
return false
s = digit_sum_base10(n)
if s == 0:
return false
return (n mod s) = 0Method comparison
| Task | Idea | Extra space |
|---|---|---|
| Single check | Digit sum + n % s == 0 | O(1) |
| Range scan | Call the same helper for each i in [L, R] | O(1) |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Next digit | sum += n % 10; n /= 10; |
| Preserve n | int original = number; before the digit loop |
| Harshad test | return original % sum == 0; |
| Reject invalid | if (number <= 0) return 0; |
| Zero sum guard | if (sum == 0) return 0; before % |
Compare
📋 Digit Sum vs Digital Root vs Other Bases
Related ideas — only the one-shot digit sum is required for Harshad.
Harshad
n % s(n)One digit sum, then divisibility
Digital root
iterate sKeep summing until one digit — not needed here
Other bases
radix bSame rule with base-b digits if the prompt asks
Interview tip
guard % 0State n > 0 and never divide by a zero sum
Context
When This Problem Shows Up
Reach for Harshad drills when digit sums and divisibility matter.
Interview warm-ups
Quick check of digit loops, modulo, and edge cases.
Digit-property family
Pairs with happy, Disarium, and other digit walks.
Checksum intuition
Digit sums appear in simple validation schemes.
Range filters
List or count Harshad numbers in
[L, R].Not digital root
Do not keep iterating until one digit unless asked.
Key benefit: a tiny problem that covers digits, divisibility, and undefined-behavior awareness in one pass.
Interactive
🔮 Live Preview
Enter a positive integer and see digit sum, remainder, and whether it is Harshad.
Hands-On
Examples Gallery
Two complete C programs — classify a single value, and list Harshad numbers in [1, 20]. Click View Output to reveal sample console results.
📚 Getting Started
Digit sum + modulus for n = 18.
Example 1 — Single Value: 18
Explicit guards so n % 0 never runs; keep original for the final test.
c
#include <stdio.h>
int digit_sum_positive(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int is_harshad(int number) {
int original = number;
int sum;
if (number <= 0) {
return 0;
}
sum = digit_sum_positive(number);
if (sum == 0) {
return 0;
}
return original % sum == 0;
}
int main(void) {
int number = 18;
if (is_harshad(number)) {
printf("%d is a Harshad number.\n", number);
} else {
printf("%d is not a Harshad number.\n", number);
}
return 0;
}How It Works
For 18, the digit sum is 9. Since 18 % 9 == 0, the function returns true (nonzero int). The early returns keep the modulus from ever seeing a zero divisor.
📈 Practical Patterns
Reuse the same helper across a closed interval.
Example 2 — Harshad Numbers in [1, 20]
Scan each i independently; listing matches the classic reference output.
c
#include <stdio.h>
int digit_sum_positive(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int is_harshad(int num) {
int original = num;
int sum;
if (num <= 0) {
return 0;
}
sum = digit_sum_positive(num);
if (sum == 0) {
return 0;
}
return original % sum == 0;
}
int main(void) {
int i;
printf("Harshad numbers in the range 1 to 20:\n");
for (i = 1; i <= 20; ++i) {
if (is_harshad(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}How It Works
11, 13, 14, 15, 16, 17, and 19 fail the final modulus test; the rest in the interval pass.
🧠 How the Algorithm Checks Harshad
1
Validate n
Require n > 0; reject non-positive inputs before any modulus.
Guard
2
Sum digits
Save original, then walk digits with % 10 / /= 10.
s(n)
3
Test divisibility
If sum > 0 and original % sum == 0, report Harshad.
Check
=
Verdict ready
For 18, s = 9 and 18 % 9 == 0 — Harshad.
Trace
🔎 Worked Walkthrough — n = 18
Trace the digit-sum loop, then the final modulus check.
| Step | n (working) | Digit | Running sum |
|---|---|---|---|
1 | 18 | 8 | 8 |
2 | 1 | 1 | 9 |
3 | 0 | — | loop ends |
4 | original 18 | — | 18 % 9 == 0 → Harshad |
By contrast, 11 has digit sum 2 and 11 % 2 != 0, so it is not Harshad.
Use Cases
Where Harshad thinking shows up beyond the interview prompt.
1. Digit Loop Practice
Build fluency with % 10 / /= 10 extraction.
Example: same helper reused for sum-of-digits problems.
2. Divisibility Warm-Ups
Combine a derived value with a modulus test.
Example: n % s(n) == 0.
3. UB Awareness
Teaches why dividing by a zero digit sum is undefined in C.
Example: guard n ≤ 0 and sum == 0.
4. Range Filters
List or count Harshad numbers in an interval.
Example: all Harshad in 1–20.
5. Other Bases
Generalize the digit extractor with radix b.
Example: Harshad-b numbers in contests.
6. Related Digit Problems
Happy, Disarium, and similar digit-property checks.
Example: previous/next interview pages.
Pro Tip: if the interviewer mentions digital roots, clarify that Harshad only needs one digit sum — not iterated reduction.
Advantages
Why this approach earns interview points.
1. Tiny Code Surface
Digit sum + one modulus — easy to write and explain.
2. O(log n) Time
Work proportional to the number of decimal digits.
3. Reusable Helper
One
is_harshadpowers single checks and range scans.4. Clear Safety Story
Guards for
n ≤ 0show you understand C’s% 0hazard.
Pro Tip: lead with the definition and the zero guard — interviewers often probe the n = 0 case.
Usage Tips
Small habits that keep Harshad code clean in interviews.
1. Require Positive n
Validate
n > 0at the API boundary before digit work.2. Copy Before Destroying
Save
originalbefore the digit loop zeroesn.3. Guard sum == 0
Belt-and-suspenders before
original % sum.4. Clarify Base 10
State the radix unless the prompt specifies another base.
5. Test 18, 11, and 1
Harshad, not Harshad, and the single-digit edge case.
Pro Tip: dry-run 18 on paper (table above) before coding — it locks in the digit walk and the final %.
Common Pitfalls
Mistakes that commonly break Harshad solutions in C.
1. Modulus by Zero
For
n = 0, digit sum is0and% 0is undefined behavior.→ Reject
n ≤ 0(and guardsum == 0) before dividing.2. Losing the Original Value
After the digit loop,
nis0— you cannot test divisibility on it.→ Keep
original(or pass a copy into the digit-sum helper).3. Treating Negatives Casually
A
while (n > 0)loop skips negative inputs entirely.→ Reject negatives, or define and document absolute-value handling.
4. Iterating to Digital Root
Harshad does not require reducing to a single digit.
→ Sum once, then test divisibility.
5. Wrong Base Assumption
Other radices change both digits and the divisor.
→ Confirm base 10 unless the prompt says otherwise.
Edge Cases
Check these inputs before calling the solution done.
n = 1
Single digit
s(1) = 1 and 1 % 1 == 0 — Harshad.
Zero
n = 0
Not a positive Harshad number; reject before the modulus.
Negatives
n < 0
Out of the usual definition; reject or document abs handling.
Not Harshad
n = 11
s = 2 but 11 % 2 != 0.
Trailing zeros
Large n
Digit sums stay small; overflow is rare if you only add digits.
Base
Radix
Clarify base 10 in APIs; other bases change both digits and the divisor.
Reference
🔄 Sample Values
Known results for common interview inputs.
n | s(n) | Harshad? |
|---|---|---|
1 | 1 | Yes |
12 | 3 | Yes |
11 | 2 | No |
18 | 9 | Yes |
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Read n from stdin
- Use
scanfand validaten > 0 - Print a clear Harshad / not-Harshad message
2. Count in a range
- How many Harshad numbers in
[1, 100]? - Reuse
is_harshad
3. Other base
- Generalize digit extraction with radix
b - Test a few known Harshad-b values
4. Multiple Harshad
- Numbers that remain Harshad after dividing by s(n)
- Optional deeper follow-up
Important
Notes
- Alias. Harshad and Niven name the same base-10 digit-sum divisibility class.
- Single-digit numbers
1..9are always Harshad becauses(n) = n. - Preserve
original, accumulatesum, guardsum != 0before%. - Harshad needs one digit sum — not a digital-root iteration unless asked.
Quick Takeaway: for positive n, sum decimal digits then test n % s == 0 — never divide by a zero digit sum.
Analysis
⏱️ Time and Space Complexity
| Task | Time | Extra space |
|---|---|---|
One n | O(log n) decimal digits | O(1) |
Scan [1, N] | O(N log N) digit work total | O(1) |
Here log n means base-10 logarithm: proportional to the number of decimal digits of n.
🎉 Conclusion
Harshad numbers are a small digit-sum exercise with clear interview payoff: extraction, divisibility, and careful zero guards in C. Master the single-check helper and the range scan so you can adapt either stop condition on the spot.
Practice the two examples above, then continue to LCM for another classic number-theory warm-up.
Keep original, sum digits, guard sum != 0, then test original % sum == 0 for positive n.
Pro Tips
💡 Best Practices
✅ Do
- State the base-10 rule before coding
- Validate
n > 0and never divide by a zero digit sum - Preserve the original value across the digit loop
- Test 18, 11, and a single-digit case
- Reuse one helper for range scans
❌ Don’t
- Call
n % 0for zero or invalid inputs - Overwrite
nthen try to test divisibility on it - Iterate digit sums to a digital root unless asked
- Assume another base without clarifying
- Skip the
n = 1edge case
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about Harshad numbers in C
Classify them the interview-friendly way.
5
Core concepts 01
Rule
n % s(n) == 0
Definition 02
Digit sum
% 10 then /= 10
Code 03
Guard
Never % 0
Safety 04
1..9
Always Harshad
Edge 05
Complexity
O(log n) digits
Analysis❓ Frequently Asked Questions
A positive integer n is a Harshad (or Niven) number in base 10 if n is divisible by the sum of its decimal digits. Example: 18 has digit sum 9 and 18 is divisible by 9.
Yes. The digit sum of 1 is 1, and 1 is divisible by 1.
For n = 0 the usual digit loop yields sum 0, and n % 0 is undefined in C. The definition is for positive integers, so reject n <= 0 before dividing.
Yes. Replace decimal digits with base-b digits and use the same divisibility test. Base-10 Harshad numbers are the common interview default.
O(log10 n) digit operations to compute the digit sum, plus O(1) for the final modulus test.
The digit sum appears in digital root ideas, but Harshad only needs one sum, not iterated reduction to a single digit.
Yes in base 10 — for n in 1..9, s(n) = n, so n % s(n) == 0 always.
The digit-sum loop divides n by 10 until it becomes 0. You need the original value for the final original % sum test.
Did you Know? 🔊
The same class of integers is often called Niven numbers in English-language sources (after Ivan Niven’s 1977 talk); Harshad comes from Sanskrit and means “joy-giver.”
Continue to LCM
Learn how to find the least common multiple using GCD in C.
About the author
8 people found this page helpful