A number is called an Automorphic Number if and only if its square ends in the same digits as the number itself.
Given a positive number N, the task is to determine if the number is an Automorphic Number or not.
Examples :
Input : 5 Output : Yes Explanation : Square of 5 is 25. Input : 76 Output : Yes Explanation : Square of 76 is 5776. Input : 7 Output : No Explanation : Square of 7 is 49.
Approach :
The idea is to generate the square of the number and keep on checking the digits from the back.
Follow the steps below to solve the problem:
- Store the square of the given number (sq).
- Loop until N becomes 0 as we have to match all digits with its square.
i) Check if (N%10 == sq%10) i.e. last digit of number = last digit of square or not
a) if not equal, return false
ii) Otherwise continue i.e. reduce number and square i.e. N = N/10 and sq = sq/10. - Return true if all digits matched.
Implementation :
// C program to check if a number is Authomorphic
#include <stdbool.h>
#include <stdio.h>
// Function to check Automorphic number
bool isAutomorphic(int N)
{
// Store the square
int sq = N * N;
// Start Comparing digits
while (N > 0) {
// Return false, if any digit of N doesn't
// match with its square's digits from last
if (N % 10 != sq % 10)
return false;
// Reduce N and square
N /= 10;
sq /= 10;
}
return true;
}
// Driver code
int main()
{
int N = 5;
isAutomorphic(N) ? printf("Yes\n") : printf("No\n");
N = 7;
isAutomorphic(N) ? printf("Yes\n") : printf("No\n");
return 0;
}
Output :
Yes No
Time Complexity : O(n)
Auxiliary Space : O(1)