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

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Set sum = 0, temp = n.
  4. Step 4: If temp > 0, go to step 5; otherwise go to step 8.
  5. Step 5: Set digit = temp % 10.
  6. Step 6: Set sum = sum + digit.
  7. Step 7: Set temp = temp / 10. Go to step 4.
  8. Step 8: If n % sum == 0, go to step 9; otherwise go to step 10.
  9. Step 9: Print n is a Harshad number. Go to step 11.
  10. Step 10: Print n is not a Harshad number.
  11. 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)

StepLineBoxnsumtempdigitOutput
13Start
26Read n18Enter n:
37sum = 0, temp = n18018
48temp > 0?18018
59digit = temp % 10180188
610sum = sum + digit188188
711temp = temp / 1018818
88temp > 0?18818
99digit = temp % 1018811
1010sum = sum + digit18911
1111temp = temp / 1018901
128temp > 0?18901
1313n % sum == 0?18901
1414Print n is a Harshad number1890118 is a Harshad number
1517Stop18901

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.

More programs

← All programs

Try AI Flowchart free →