Automorphic Number — Solution in Python, Java & C++
Automorphic Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on strings and math.
Automorphic Number is an easy coding problem on strings and math, asked in TCS, Capgemini and Cognizant interviews.
- Difficulty: Easy
- Topics: Strings, Math
- Asked at: TCS, Capgemini, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A number is automorphic when its square ends with the number itself.
Given a positive integer n, return true if n is automorphic.
Example 1
Input: n = 25
Output: true
Explanation: 25² = 625, which ends in 25.
Example 2
Input: n = 7
Output: false
Explanation: 7² = 49, which does not end in 7.
Example 3
Input: n = 76
Output: true
Explanation: 76² = 5776.
Constraints
1 <= n <= 100000
Hints for Automorphic Number
Hint 1
You do not need string comparison:
n²ends withnexactly whenn² mod 10^d == n, wheredis the digit count ofn.Hint 2
Compute 10^d by counting digits, then take one modulo.
Hint 3
Comparing the tail of
str(n*n)withstr(n)is the same test written differently.
How to solve Automorphic Number
n² ends with n exactly when n² mod 10^d == n, where d is the number of digits of n.
Approach
- Compute
power = 10^dby counting digits ofn. - Return
(n * n) % power == n.
Why it works
Taking a number modulo 10^d keeps its last d decimal digits and discards the rest, so the congruence is precisely the statement that the trailing d digits of the square spell out n.
Complexity
- Time —
O(d) - Space —
O(1)
Pitfalls
n * ncan overflow a 32-bit int fornabove 46340 — use a wider type where the language has fixed widths.- Comparing string suffixes is equivalent but allocates.
Reference solution
Python
def isAutomorphic(n: int) -> bool:
power = 1
x = n
while x > 0:
power *= 10
x //= 10
return (n * n) % power == nJava
public static boolean isAutomorphic(int n) {
long power = 1;
int x = n;
while (x > 0) {
power *= 10;
x /= 10;
}
return ((long) n * n) % power == n;
}C++
bool isAutomorphic(int n) {
long long power = 1;
int x = n;
while (x > 0) {
power *= 10;
x /= 10;
}
return ((long long) n * n) % power == (long long) n;
}JavaScript
var isAutomorphic = function(n) {
let power = 1, x = n;
while (x > 0) {
power *= 10;
x = Math.floor(x / 10);
}
return (n * n) % power === n;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings