10433 - Automorphic Numbers

[altertain]

Could anybody tell me AC answer about this input?

0
1
0000
0001
0005
0076

I'm very confused with the problem statement.

[Jan]

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.

[annhy]

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]

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]

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.

[marekmosiewicz]

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]

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.

[masum93]

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]

My code and the problem statement does not consider 1 to be an automorphic number.

[uvasarker]

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]

None of the numbers you posted are automorphic.

[Mukit Chowdhury]

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