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?

Post by altertain » Fri Jun 22, 2007 1:37 pm

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:

Post by Jan » Fri Jun 22, 2007 7:57 pm

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

Post by annhy » Sat Jul 14, 2007 9:41 am

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

Post by aeiou » Thu Jun 12, 2008 9:37 am

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

Post by DD » Tue Nov 04, 2008 6:15 pm

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

Post by marekmosiewicz » Sat Oct 10, 2009 11:23 pm

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

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

Re: 10433 - Automorphic Numbers

Post by plamplam » Fri Mar 30, 2012 11:27 am

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

Post by masum93 » Wed Apr 25, 2012 1:08 am

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

Post by brianfry713 » Thu Apr 26, 2012 2:10 am

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

Post by uvasarker » Mon Nov 26, 2012 9:19 pm

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

Post by brianfry713 » Fri Nov 30, 2012 7:06 am

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

Post by Mukit Chowdhury » Wed Nov 01, 2017 7:07 pm

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

Post Reply

Return to “Volume 104 (10400-10499)”