Harshad (Niven) Number: flowchart, algorithm and program
This program reads n, adds up its digits, and checks whether n divides evenly by that digit sum. If n % sum == 0, n is a Harshad (Niven) number.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set sum = 0, temp = n.
- Step 4: If temp > 0, go to step 5; otherwise go to step 8.
- Step 5: Set digit = temp % 10.
- Step 6: Set sum = sum + digit.
- Step 7: Set temp = temp / 10. Go to step 4.
- Step 8: If n % sum == 0, go to step 9; otherwise go to step 10.
- Step 9: Print n is a Harshad number. Go to step 11.
- Step 10: Print n is not a Harshad number.
- Step 11: Stop.
Pseudocode
BEGIN
READ n
sum ← 0, temp ← n
WHILE temp > 0 DO
digit ← temp % 10
sum ← sum + digit
temp ← temp / 10
END WHILE
IF n % sum == 0 THEN
PRINT n is a Harshad number
ELSE
PRINT n is not a Harshad number
END IF
END
Program in C, Python and Java
Harshad (Niven) Number program in C
#include <stdio.h>
int main() {
int n, temp, digit, sum = 0;
printf("Enter n: ");
scanf("%d", &n);
temp = n;
while (temp > 0) {
digit = temp % 10;
sum = sum + digit;
temp = temp / 10;
}
if (n % sum == 0)
printf("%d is a Harshad number\n", n);
else
printf("%d is not a Harshad number\n", n);
return 0;
}Harshad (Niven) Number program in Python
n = int(input("Enter n: "))
temp = n
total = 0
while temp > 0:
digit = temp % 10
total = total + digit
temp = temp // 10
if n % total == 0:
print(n, "is a Harshad number")
else:
print(n, "is not a Harshad number")Harshad (Niven) Number program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
int temp = n;
int digit, sum = 0;
while (temp > 0) {
digit = temp % 10;
sum = sum + digit;
temp = temp / 10;
}
if (n % sum == 0)
System.out.println(n + " is a Harshad number");
else
System.out.println(n + " is not a Harshad number");
}
}
Sample input: n = 18
Output: Enter n: 18 is a Harshad number
How it works
- Copy n into temp so the original n is kept for the final check. The loop destroys temp, not n.
- Inside while (temp > 0), digit = temp % 10 picks off the last digit, and sum = sum + digit adds it to the running total.
- temp = temp / 10 drops the last digit. When temp reaches 0, every digit has been added and the loop stops.
- For n = 18: digits 8 and 1 give sum = 9. Then 18 % 9 == 0, so it prints that 18 is a Harshad number.
- The final check uses the original n, not temp, because temp is 0 after the loop.
Dry run (trace table)
| Step | Line | Box | n | sum | temp | digit | Output |
|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | |||||
| 2 | 6 | Read n | 18 | Enter n: | |||
| 3 | 7 | sum = 0, temp = n | 18 | 0 | 18 | ||
| 4 | 8 | temp > 0? | 18 | 0 | 18 | ||
| 5 | 9 | digit = temp % 10 | 18 | 0 | 18 | 8 | |
| 6 | 10 | sum = sum + digit | 18 | 8 | 18 | 8 | |
| 7 | 11 | temp = temp / 10 | 18 | 8 | 1 | 8 | |
| 8 | 8 | temp > 0? | 18 | 8 | 1 | 8 | |
| 9 | 9 | digit = temp % 10 | 18 | 8 | 1 | 1 | |
| 10 | 10 | sum = sum + digit | 18 | 9 | 1 | 1 | |
| 11 | 11 | temp = temp / 10 | 18 | 9 | 0 | 1 | |
| 12 | 8 | temp > 0? | 18 | 9 | 0 | 1 | |
| 13 | 13 | n % sum == 0? | 18 | 9 | 0 | 1 | |
| 14 | 14 | Print n is a Harshad number | 18 | 9 | 0 | 1 | 18 is a Harshad number |
| 15 | 17 | Stop | 18 | 9 | 0 | 1 |
Time and space complexity
Time: O(log n) · Space: O(1). The loop runs once per decimal digit of n, which is about log10(n) times, using only a few variables.
Common mistakes
- Dividing temp instead of n at the end. After the loop temp is 0, so the check is wrong (and n % sum is the one you need).
- Forgetting to initialise sum = 0, so the digit sum starts from a garbage value.
- Not handling n = 0 or negative input. The loop never runs, sum stays 0, and n % sum divides by zero, which crashes the program.
Viva questions
Q1. What is a Harshad (Niven) number? Give an example.
It is a number that is divisible by the sum of its own digits. For example, 18 is Harshad because 1+8 = 9 and 18 is divisible by 9.
Q2. Why is sum initialised to 0, and why do you copy n into temp?
sum starts at 0 because it is an accumulator and 0 is the neutral value for addition. We copy n into temp because the loop destroys the number by dividing it, and we still need the original n for the final divisibility check and the printout.
Q3. What do temp % 10 and temp / 10 do in the loop?
temp % 10 gives the last digit, which is added to sum. temp / 10 is integer division, so it drops the last digit and moves on to the next one.
Q4. When does the while loop stop, and how many times does it run?
It stops when temp becomes 0, because the condition temp > 0 is then false. It runs once for each digit of n.
Q5. What happens if the user enters 0 in this program?
The loop never runs, so sum stays 0, and then n % sum is a modulo by zero. This is undefined behaviour and usually crashes the program with a floating point exception. We should check for n <= 0 first, or handle it separately.
Q6. What happens if the user enters a negative number, like -18?
The condition temp > 0 is false at the start, so sum remains 0 and the program again does n % 0, which is a crash. Harshad numbers are defined for positive integers, so we should reject n <= 0 with a message.
Q7. What is the time complexity of this program?
It is O(d), where d is the number of digits of n, which is the same as O(log n) in base 10. The loop removes one digit per iteration and everything else is constant time. The extra space is O(1).
Q8. What would you change to test Harshad in another base, say base 8 or base 2?
Replace the 10 in temp % 10 and temp / 10 with the base b. The digit sum is then taken in base b and the divisibility check on n stays the same.
Frequently asked questions
What is a Harshad number?
A Harshad (or Niven) number is a number that is divisible by the sum of its digits. For example, 18 is one because 1 + 8 = 9 and 18 is divisible by 9.
Why do we copy n into temp?
The loop keeps dividing the number by 10 until it becomes 0. Working on a copy keeps the original n available for the final n % sum check and the printed message.
What happens if n is 0 or negative in this code?
The while (temp > 0) loop is skipped, so sum stays 0. Then n % sum divides by zero, which is undefined behaviour. Add a check that n > 0 before running the loop.