## 10433 - Automorphic Numbers

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

### Could you tell me AC answer about this input?

Could anybody tell me AC answer about this input?

0
1
0000
0001
0005
0076

I'm very confused with the problem statement.
Lee, Taeyoon

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
My accepted code returns...

Output:

Code: Select all

``````Not an Automorphic number.
Automorphic number of 1-digit.
Not an Automorphic number.
Not an Automorphic number.
Not an Automorphic number.
Not an Automorphic number.``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan
razibcse wrote:I got this problem AC...
I first generated both the 2000-digit automorphic numbers in a seperate program because it took a lot of time...then I checked
the digits from the last with the digits of input number,because an automorphic number contains all the smaller automorphic numbers...
I use the same method to solve, by pre-computing the 2000-digit automorphic numbers by using BigInteger in Java.
But I got WA for a lots of times, and finally get AC after three hours later.

To whom get WA for the same reason:
If your source code contains a line longer than 990 characters,
the judge system will add additional CRLF on it,
and the modified source code can still pass the compiling process.

aeiou
New poster
Posts: 21
Joined: Wed May 07, 2008 11:32 am

### 10433 - Automorphic Numbers

Hi everbody ,

I tried to solve this problem in JAVA but I get TLE...

I proceed like this :
1. I use BigInt mutiplication to square the number.
2. Obtain a substring from the square and compare it with the original number..

Here's my code...Anyone pls help me!!!

Code: Select all

``````import java.math.*;
import java.io.*;

class Main
{
public static BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException
{
while ( true )
{
String num = stdin.readLine ();
if ( num == null )
break;

BigInteger x = new BigInteger (num);
x = x.multiply (x);

String mul = x.toString();
String mult = mul.substring ( mul.length() - num.length() );
if ( mult.equals (num) )
System.out.println ( "Automorphic number of " + num.length() + "-digit.");
else
System.out.println ( "Not an Automorphic number.");

}
}
}

``````
Waiting for help !!
Thanks in advance....

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10433 - Automorphic Numbers

aeiou wrote:Hi everbody ,

I tried to solve this problem in JAVA but I get TLE...

I proceed like this :
1. I use BigInt mutiplication to square the number.
2. Obtain a substring from the square and compare it with the original number..

Here's my code...Anyone pls help me!!!

Code: Select all

``````import java.math.*;
import java.io.*;

class Main
{
public static BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException
{
while ( true )
{
String num = stdin.readLine ();
if ( num == null )
break;

BigInteger x = new BigInteger (num);
x = x.multiply (x);

String mul = x.toString();
String mult = mul.substring ( mul.length() - num.length() );
if ( mult.equals (num) )
System.out.println ( "Automorphic number of " + num.length() + "-digit.");
else
System.out.println ( "Not an Automorphic number.");

}
}
}

``````
Waiting for help !!
Thanks in advance....
According to my experiences, it is very hard to pass the time limit if you directly multiple two big integer and check the result is a automorphic number or not. Besides, it is also troublesome to check the product of multiplication when input has leading zeros. So I recommand that you can try another method to solve this problem. Good luck!

P.S. Although I solved this problem by multiplication but it costs me a lot of efforts to deal with correctness and speed issues.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

marekmosiewicz
New poster
Posts: 1
Joined: Sat Oct 10, 2009 11:15 pm

### Re: 10433 - Automorphic Numbers

Many years ago I found algorithm which generates automorphic number n from automorphic number n-1 in O(n) time.
I can't find it anywhere so I public it here too:

Code: Select all

``````/*
* Automorphic number generator in Java
* Tested up to 150000 numbers with Java BigInteger
*/
package automorphic;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.logging.Level;
import java.util.logging.Logger;

//Context of search
/**
* @author Marek Mosiewicz(marek.mosiewicz[at]jotel.com.pl)
*      It is simple standard multiplication algorithm
*      The only difference is that no repeats
*      for multiplication for part already done
*      (only appending digits at the beginig to try).
*      Adds new numbers at the beginig and perfoms only
*      necessery multpilication + aggregates with already
*      done sum of previos multiplication for this column
*      Optimizations in case when 0 number found possible
*      (I currently search prefix for all combinations as long as
*      not next automorphic number is found)
*      Linearar complexity for finding n-th element from n-1 element
*      Ported from oryginal Turbo Pascal - oryginal tables were [1..MAX] - preserved
*/
public class Generator {
//Start number can be 5 or 6 - determines which of two sequences will generate
private static int START_NUMBER = 5;
//Max number of digits to remember
public static int MAX = 1000000;
//search for TARGET iterations
//(numbers of digits does not match
//becouse we search for combination in case of 0)
public static int TARGET = 900000;

//search if given combination is automorphic number
private static boolean isMorphic(Operational o) {
int[] tempAggregates = new int[MAX + 20 -o.searchPostion];  //reserve
int m;
int n;
int result = 0;
//copy temporary array of aggregation in case we will not
//find good number
System.arraycopy(o.aggregates, 0, tempAggregates, 0, MAX - o.searchPostion+18); //18 + reserve
int combinationStart = MAX + 1 - o.foundPosition;
int combinationEnd = MAX + 1 - o.searchPostion;
long tempAggregate = o.leadingAggregate;
//for all combinations of searched prefix
for (int x = combinationStart + 1; x <= combinationEnd; x++) {
n = MAX;
m = MAX - x + 1;
long sum = 0;
for (int y = 1; y <= x; y++) {
result = (o.morphicNumber[n] * o.morphicNumber[m]) + tempAggregates[y];
int modulo = result % 10;
sum = sum + modulo;
//new aggregate
tempAggregates[y] = (result - modulo) / 10;
m++;
n--;
}
sum = sum + tempAggregate;
long modulo = sum % 10;
tempAggregate = (sum - modulo) / 10;
sum = sum % 10;
//if digit match
if (sum != o.morphicNumber[MAX + 1 - x]) {
return false;
}
}
//new aggregates are correct
o.aggregates = tempAggregates;
o.leadingAggregate = tempAggregate;
return true;
}
/**
* Increment number. In case of switching from 9-0
* starts combination search which is to be avoided
* probably, but degradation of performance is not observed
* @param o
*/
private static void increment(Operational o) {
boolean koniec = false;
int i = o.foundPosition - 1;
while (!koniec) {
if (o.morphicNumber[i] != 9) {
o.morphicNumber[i] = o.morphicNumber[i] + 1;
koniec = true;
} else {
o.morphicNumber[i] = 0;
if (i <= o.searchPostion) {
koniec = true;
}
i--;
}
}
if (i < o.searchPostion) {
o.searchPostion = i;
}
}
/**
* Prints number to file
* @param output - file
* @param o - operational context
*/
private static void print(Writer output, Operational o) {
try {
for (int i = o.searchPostion; i <= MAX; i++) {
output.append(Integer.toString(o.morphicNumber[i]));
}
output.append('\n');
} catch (IOException ex) {
Logger.getLogger(Generator.class.getName()).log(Level.SEVERE, null, ex);
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Operational o = new Operational();
try {
Writer output = new BufferedWriter(new FileWriter("morphic.txt"));

for (int i = 0; i <= MAX; i++) {
o.aggregates[i] = 0;
o.morphicNumber[i] = 0;
}
//seed
o.morphicNumber[MAX] = START_NUMBER;
int i = 0;
while(i<TARGET) {
//save only every 1000 iterations to not degrade performance
//iteration is not equal digit in case of zeros
if (isMorphic(o)) {
if (i % 1000 == 0) {
print(output, o);
System.out.println("Automorphic number nr:"+i+" found.");
}
i++;
o.foundPosition = o.searchPostion;
}
//increment value
increment(o);
}
output.close();
} catch (IOException ex) {
Logger.getLogger(Generator.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
class Operational {
int[] morphicNumber = new int[Generator.MAX + 1];
int[] aggregates = new int[Generator.MAX + 1];
long leadingAggregate = 0;
//cuurent postion we look for
int searchPostion = Generator.MAX;
//current position of calculated automorphic number
int foundPosition = Generator.MAX + 1;
}
``````
It seems that automorphic number in english wikipedia is not proper at the begining (first 900+ digits are ok).

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10433 - Automorphic Numbers

I got accepted with java, just squared the input using biginteger multiplication. Note that, I didn't use substring but a loop to check.
Also take the input as string to conserve leading zeros. The length of the squared number might be less then the original number, which if you don't check will lead to runtime error. Consider the input 001, the square of which is 1.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

masum93
New poster
Posts: 7
Joined: Wed May 11, 2011 11:15 am

### Re: 10433 - Automorphic Numbers

Code: Select all

``````import java.math.*;
import java.util.*;

public class Main {
public static void main(String[] args){
Scanner big = new Scanner(System.in);
BigInteger zero = new BigInteger("0");
while(true){
try{
String str = big.nextLine();
int len = str.length();
BigInteger n = new BigInteger(str);
int y = n.intValue();
if(y == 0){
System.out.println("Not an Automorphic number.");
continue;
}
BigInteger m = n.multiply(n);
BigInteger x = m.subtract(n);
BigInteger b = new BigInteger("10");
BigInteger num = b.pow(len);
BigInteger rem = x.remainder(num);
String s = "Automorphic number of ";
s += len;
s += "-digit.";
if(rem.compareTo(zero) == 0)	System.out.println(s);
else System.out.println("Not an Automorphic number.");
}
catch(NoSuchElementException vr1){
break;
}
}
}
}
``````
I need some test cases. My code passes the above cases stated earlier.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10433 - Automorphic Numbers

My code and the problem statement does not consider 1 to be an automorphic number.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

### Re: 10433 - Automorphic Numbers

I have no idea about it's 2nd statement:
what is the square value of these following numbers:
0
1
0000
0001
0005
0076

Same like as?
00
1
00000000
0000001
00000025
00005776

Or Not?
Please, help me according to this problem.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10433 - Automorphic Numbers

None of the numbers you posted are automorphic.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 10433 - Automorphic Numbers

I made this code AC using Java BigInteger class. I used pow() for getting square. Also used substring method.