Automorphic Number: flowchart, algorithm and program
This program reads n, squares it, and checks whether the last digits of the square are exactly n. For example, 25 squared is 625, which ends in 25, so 25 is automorphic.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Set divisor = 1.
- Step 3: Read n.
- Step 4: Set sq = n * n, temp = n.
- Step 5: If temp == 0, go to step 6; otherwise go to step 7.
- Step 6: Set divisor = 10.
- Step 7: If temp > 0, go to step 8; otherwise go to step 10.
- Step 8: Set divisor = divisor * 10.
- Step 9: Set temp = temp / 10. Go to step 7.
- Step 10: If sq % divisor == n, go to step 11; otherwise go to step 12.
- Step 11: Print n is Automorphic. Go to step 13.
- Step 12: Print n is not Automorphic.
- Step 13: Stop.
Pseudocode
BEGIN
divisor ← 1
READ n
sq ← n * n, temp ← n
IF temp == 0 THEN
divisor ← 10
END IF
WHILE temp > 0 DO
divisor ← divisor * 10
temp ← temp / 10
END WHILE
IF sq % divisor == n THEN
PRINT n is Automorphic
ELSE
PRINT n is not Automorphic
END IF
END
Program in C, Python and Java
Automorphic Number program in C
#include <stdio.h>
int main() {
long long n, sq, temp, divisor = 1;
printf("Enter n: ");
scanf("%lld", &n);
sq = n * n;
temp = n;
if (temp == 0)
divisor = 10;
while (temp > 0) {
divisor = divisor * 10;
temp = temp / 10;
}
if (sq % divisor == n)
printf("%lld is an Automorphic number\n", n);
else
printf("%lld is not an Automorphic number\n", n);
return 0;
}Automorphic Number program in Python
n = int(input("Enter n: "))
sq = n * n
temp = n
divisor = 1
if temp == 0:
divisor = 10
while temp > 0:
divisor = divisor * 10
temp = temp // 10
if sq % divisor == n:
print(n, "is an Automorphic number")
else:
print(n, "is not an Automorphic number")Automorphic 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: ");
long n = sc.nextLong();
long sq = n * n;
long temp = n;
long divisor = 1;
if (temp == 0)
divisor = 10;
while (temp > 0) {
divisor = divisor * 10;
temp = temp / 10;
}
if (sq % divisor == n)
System.out.println(n + " is an Automorphic number");
else
System.out.println(n + " is not an Automorphic number");
}
}
Sample input: n = 25
Output: 25 is an Automorphic number
How it works
- Read n and compute sq = n * n. For n = 25 this gives sq = 625.
- Build divisor, a power of 10 with as many digits as n. Start with divisor = 1, then loop: while temp > 0, multiply divisor by 10 and cut a digit off temp with temp / 10. For 25 the loop runs twice, so divisor = 100.
- Take sq % divisor to keep only the last digits of the square. 625 % 100 = 25.
- If that remainder equals n (25 == 25), print that n is an Automorphic number. Otherwise print that it is not.
- The special case n = 0 sets divisor = 10, because the loop never runs for 0 and divisor would stay 1. Then 0 % 10 == 0 works out correctly.
Dry run (trace table)
| Step | Line | Box | divisor | n | sq | temp | Output |
|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | |||||
| 2 | 4 | divisor = 1 | 1 | ||||
| 3 | 6 | Read n | 1 | 25 | Enter n: | ||
| 4 | 8 | sq = n * n, temp = n | 1 | 25 | 625 | 25 | |
| 5 | 9 | temp == 0? | 1 | 25 | 625 | 25 | |
| 6 | 11 | temp > 0? | 1 | 25 | 625 | 25 | |
| 7 | 12 | divisor = divisor * 10 | 10 | 25 | 625 | 25 | |
| 8 | 13 | temp = temp / 10 | 10 | 25 | 625 | 2 | |
| 9 | 11 | temp > 0? | 10 | 25 | 625 | 2 | |
| 10 | 12 | divisor = divisor * 10 | 100 | 25 | 625 | 2 | |
| 11 | 13 | temp = temp / 10 | 100 | 25 | 625 | 0 | |
| 12 | 11 | temp > 0? | 100 | 25 | 625 | 0 | |
| 13 | 15 | sq % divisor == n? | 100 | 25 | 625 | 0 | |
| 14 | 16 | Print n is Automorphic | 100 | 25 | 625 | 0 | 25 is an Automorphic number |
| 15 | 19 | Stop | 100 | 25 | 625 | 0 |
Time and space complexity
Time: O(log n) · Space: O(1). The loop removes one digit of n per iteration, so it runs about log10(n) times using only a few variables.
Common mistakes
- Taking sq % 10 or comparing only the last digit. You must compare as many digits as n has, so divisor has to be 10 raised to the number of digits in n.
- Changing n while counting digits. Use the copy temp for the loop, because you still need the original n for the final comparison.
- Forgetting n = 0. The while loop does not run for 0, so divisor would stay 1 unless you handle it separately.
- Using int for larger n. The square overflows quickly, which is why the code uses long long.
Viva questions
Q1. What is an automorphic number? Give an example from this program's point of view.
A number whose square ends with the number itself. For example 25: 25 squared is 625, which ends in 25. The program checks this using sq % divisor == n.
Q2. Why is divisor initialised to 1 and not 0?
Because divisor is multiplied by 10 once per digit. Starting at 1 gives 10^digits (for 25, 1 -> 10 -> 100). If it started at 0 it would stay 0 and the modulus would be invalid.
Q3. What does the while loop do, and why do we copy n into temp?
It counts the digits of n by dividing temp by 10 until it becomes 0, multiplying divisor by 10 each time. We use temp so that n is not destroyed, since we still need n for the final comparison and printing.
Q4. Why does sq % divisor give the last digits of the square?
Taking a number modulo 10^d returns the remainder after dividing by 10^d, which is exactly its last d digits. With d equal to the digit count of n, we get the last digits of n*n to compare with n.
Q5. What is the purpose of the if (temp == 0) divisor = 10; line, and what happens for n = 0 and n = 1?
The while loop does not run for 0, so without this line divisor would stay 1 and sq % 1 is always 0. Setting it to 10 handles one digit. For n = 0, sq = 0 and 0 % 10 == 0, so it is automorphic. For n = 1, divisor is 10, sq = 1, 1 % 10 == 1, so it is automorphic.
Q6. What happens if the user enters a negative number, for example -5?
The while loop condition temp > 0 is false, so divisor stays 1 and sq % 1 is 0, which is not equal to -5. The program prints 'not Automorphic', which is acceptable since automorphic numbers are defined for non-negative integers, though it does not validate input.
Q7. Why is long long used, and what limitation remains?
n*n can be very large, so long long avoids overflow for bigger inputs than int allows. It can still overflow if n is above about 3 billion, giving wrong results.
Q8. What is the time complexity of this program? What would change if you wanted to check automorphism using a recursive or string method instead?
It is O(d), where d is the number of digits of n (about log10 n), because the loop runs once per digit; the rest is constant time. A string method would convert n and n*n to strings and compare the ending characters, which is also O(d) but uses extra memory.
Frequently asked questions
What is an automorphic number?
It is a number whose square ends with the number itself. For example 5 (25), 6 (36), 25 (625) and 76 (5776) are automorphic.
Why do we use a divisor like 10, 100 or 1000?
Taking sq % divisor keeps exactly the last k digits of the square, where k is the number of digits in n. You can then compare those digits directly with n.
Why is there a special case for n = 0?
The digit-counting loop only runs while temp > 0, so for 0 it never runs and divisor stays 1. Setting divisor = 10 makes 0 % 10 == 0 and so 0 is reported as automorphic.