10433  Automorphic Numbers
Moderator: Board moderators
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.
0
1
0000
0001
0005
0076
I'm very confused with the problem statement.
Lee, Taeyoon
My accepted code returns...
Output:
Hope it helps.
Output:
Code: Select all
Not an Automorphic number.
Automorphic number of 1digit.
Not an Automorphic number.
Not an Automorphic number.
Not an Automorphic number.
Not an Automorphic number.
Ami ekhono shopno dekhi...
HomePage
HomePage
I use the same method to solve, by precomputing the 2000digit automorphic numbers by using BigInteger in Java.razibcse wrote:I got this problem AC...
I first generated both the 2000digit 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...
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.
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!!!
Waiting for help !!
Thanks in advance....
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.");
}
}
}
Thanks in advance....

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 10433  Automorphic Numbers
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!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!!!
Waiting for help !!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."); } } }
Thanks in advance....
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 realworld problems?

 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 n1 in O(n) time.
I can't find it anywhere so I public it here too:
It seems that automorphic number in english wikipedia is not proper at the begining (first 900+ digits are ok).
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 nth element from n1 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 90
* 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;
}
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.
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
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;
}
}
}
}

 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!

 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.
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.

 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!

 Learning poster
 Posts: 99
 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.