All challenges
Easy 0 solved 0% acceptance

Automorphic Number

Check whether the square of a number ends with the number itself.

What you'll learn

  • Count the digits of a number
  • Take the last d digits with a modulo
  • Handle 0 as a one-digit number

Problem

A number is automorphic if its square ends in the same digits as the number. For example, 76² = 5776, which ends in 76, so 76 is automorphic.

Implement automorphic_number(n).

n² can be as large as 10^18, which still fits in a signed 64-bit integer. You can compare digits from the right, or compare n² modulo 10^d with n, where d is the number of digits of n.

Input

n: The number to test.

Output

Return true if the last digits of n² are exactly the digits of n, otherwise false. 0 and 1 are automorphic (0² = 0, 1² = 1).

Constraints

0 ≤ n ≤ 10^9

Examples

Example 1
Input:
n = 25

Expected output:
expected = True
Input:
long long n = 25;

Expected output:
bool expected = true;
Input:
long n = 25;

Expected output:
bool expected = true;

Explanation

25² = 625, which ends in 25, so the answer is true.

Example 2
Input:
n = 7

Expected output:
expected = False
Input:
long long n = 7;

Expected output:
bool expected = false;
Input:
long n = 7;

Expected output:
bool expected = false;

Explanation

7² = 49, which ends in 9, not 7, so the answer is false.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Find how many digits n has.

Hint 2

The last d digits of a number are its remainder modulo 10^d.

Hint 3

Make sure n = 0 counts as one digit, so 10^d is 10, not 1.

Expected complexity

O(d) time for d digits, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.