FOR FREE CONTENT
Automorphic Number in a range
Back to ProgrammingDescription
Before seeing the program please follow the program check automorphic number.
A number is said to be an automorphic number if the number is present in the last digit(s) of the square of the original number.
If the number is 25, the square of 25 is 625 in which the last two digits contain the original number i.e. 25. Therefore, this number is an automorphic number.
If the number is 20, the square of 20 is 400 which does not contain 20 in its last digit(s). Therefore, 20 is not an automorphic number.
For this program, the ranges are taken as input, for each number between the ranges; the square of the number is calculated. After that, it is checked that the square contains the original number in its last digit(s) or not. If it contains then the number is displayed as the output, otherwise not.
Algorithm
INPUT: The ranges
OUTPUT: The automorphic numbers between the given ranges
PROCESS:
Step 1: [Taking the inputs]
Read m, n [The ranges]
Step 2: [Checking for automorphic number]
For i=m to n repeat
[Calculating the square of the number]
Set s<-i2
Set tmp<-i
[Checking for automorphic number]
While i>0 repeat
[Comparing the digits of the number with its square]
If (s mod 10)≠(i mod 10) then
Break
[End of ‘if’]
Set s<-s/10
Set i<-i/10
[End of ‘while’ loop]
[Printing the output according to the proper condition]
If i=0 then
Print tmp
[End of ‘if’]
Set i<-tmp
[End of ‘for’ loop]
Step 3: Stop.
Code
Time Complexity:
for(i=m;i<=n;i++)-----------------------------------------O(p)
{ //calculating the square of the number
s=i*i;
tmp=i;
//checking for automorphic number
while(i>0)---------------------------------------O(k) [‘k’ is the number of digits]
{ //comparing the digits of the
//number with its square
if((s%10)!=(i%10))
break;
s=s/10;
i=i/10;
}
//printing the output according to the proper condition
if(i==0)---------------------------------------------------O(1)
printf("%d ",tmp);
i=tmp; }
The time complexity of this program is O(p*k) where ‘p’ is the numbers between the ranges, and ‘k’ is the number of digits of each number between the range that is to be checked for the automorphic number.
Space Complexity:
The space complexity of this program is O(1) as it requires a constant number of spaces to execute for any given input.
