Automorphic Number

Easy
168.

Automorphic Number

Automorphic Number is an easy coding problem on strings and math, asked in TCS, Capgemini and Cognizant interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var isAutomorphic = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    You do not need string comparison: n² ends with n exactly when n² mod 10^d == n, where d is the digit count of n.

  2. Hint 2

    Compute 10^d by counting digits, then take one modulo.

  3. Hint 3

    Comparing the tail of str(n*n) with str(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

  1. Compute power = 10^d by counting digits of n.
  2. 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 * n can overflow a 32-bit int for n above 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 == n

Java

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