10527 - Persistent Numbers

[jumbo]

Hello,

I'd like to ask if I can use BigInteger class from package java.math.BigInteger in Java. I'm not getting any compilation error or runtime error, I am getting WA, so I assume that it is ok to use it, but just for assure.

So can you look at my code and help me:

Code: Select all

import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    // processing number
    private BigInteger processing;
    
    // all the input
    private ArrayList<BigInteger> in;
    
    // static BigInteger representation of some numbers 
    private static final BigInteger twoVal = new BigInteger("2");
    private static final BigInteger threeVal = new BigInteger("3");
    private static final BigInteger fiveVal = new BigInteger("5");
    private static final BigInteger sevenVal = new BigInteger("7");
    private static final BigInteger oneVal = new BigInteger("1");
    private static final BigInteger fourVal = new BigInteger("4");
    private static final BigInteger sixVal = new BigInteger("6");
    private static final BigInteger eightVal = new BigInteger("8");
    private static final BigInteger nineVal = new BigInteger("9");
    private static final BigInteger tenVal = new BigInteger("10");
    
    // counts of the one digit primes in the prcessing NUM
    private BigInteger twoCount = new BigInteger("0");
    private BigInteger threeCount = new BigInteger("0");
    private BigInteger fiveCount = new BigInteger("0");
    private BigInteger sevenCount = new BigInteger("0");

    
    public Main()
    {
        in = new ArrayList<BigInteger>();
    }
    
    // reads all the avialable bytes from System.in (as far as -1)
    public void readInput()
    {
        try
        {
            //pole pro nacteni celeho vstupu naraz
            byte[] b = new byte[System.in.available()];
            
                int r = System.in.read(b);
                if (r == -1) 
                {
                    System.exit(1);
                }
                
                StringTokenizer tok = new StringTokenizer(new String(b));
                
                // pocet radku, standartni delimitery staci
                int radku = tok.countTokens();
                // int pro ulozeni radku
                BigInteger tmp;
                for (int i = 0; i < radku; i++) 
                {
                    // dostanu jeden radek jako string a udelam z nej int
                    tmp = new BigInteger(tok.nextToken());
                    // pri nule je konec, davaji za nulu jeste dalsi cisla...
                    if( tmp.intValue() == -1 ) break;
                    // pridam do arraylistu
                    in.add(tmp);
                    
                }
                
            
        } 
        catch (IOException ex) 
        {
                System.out.println("chyba");
                System.exit(1);
        }
    }
   
    // just sets the field
    public void setNum(BigInteger n)
    {
        processing = n;
    }
    
    // divides the number by one digit primes (2, 3, 5, 7) and counts how many times NUM was 
    // divided by each of the prime
    public void getParts()
    {
        if(processing.intValue() == 0)
            return;
        
        BigInteger tmp = processing;          
        

        while(processing.remainder(twoVal).intValue() == 0 )
        {
            twoCount = twoCount.add(oneVal);
            processing = processing.divide(twoVal);
        }
        while(processing.remainder(threeVal).intValue() == 0 )
        {
            threeCount = threeCount.add(oneVal);
            processing = processing.divide(threeVal);
        }
        while(processing.remainder(fiveVal).intValue() == 0 )
        {
            fiveCount = fiveCount.add(oneVal);
            processing = processing.divide(fiveVal);
        }
        while(processing.remainder(sevenVal).intValue() == 0 )
        {
            sevenCount = sevenCount.add(oneVal);
            processing = processing.divide(sevenVal);
        }
        
        processing = tmp;
    }
    
       
    // check if all of the parts we got multiplied give the original number
    public boolean check()
    {
        BigInteger  chck = new BigInteger("0");

	
        BigInteger tmp1 = sevenVal.pow(sevenCount.intValue());
        BigInteger tmp2 = fiveVal.pow(fiveCount.intValue());
        BigInteger tmp3 = threeVal.pow(threeCount.intValue());
        BigInteger tmp4 = twoVal.pow(twoCount.intValue());

        chck = tmp1.multiply(tmp2.multiply(tmp3.multiply(tmp4)));
	
        if ( chck.equals(processing) )
            return true;
        
        return false;
    }
    
    // method that builds the smallest number from the parts
    public BigInteger createPrevious()
    {
        BigInteger prev = new BigInteger("0");
        BigInteger digit_place = new BigInteger("1");
        
        if (processing.intValue() == 1)
            return new BigInteger("11");
        
        while(contains(9))
        {
            prev = prev.add(digit_place.multiply(nineVal));
            digit_place= digit_place.multiply(tenVal);
            threeCount = threeCount.subtract(twoVal);
        }
        while(contains(8))
        {
            prev = prev.add(digit_place.multiply(eightVal));
            digit_place= digit_place.multiply(tenVal);
            twoCount = twoCount.subtract(threeVal);
        }
        while(contains(7))
        {
            prev = prev.add(digit_place.multiply(sevenVal));
            digit_place= digit_place.multiply(tenVal);
            sevenCount = sevenCount.subtract(oneVal);
        }
        while(contains(6))
        {
            prev = prev.add(digit_place.multiply(sixVal));
            digit_place= digit_place.multiply(tenVal);
            threeCount = threeCount.subtract(oneVal); 
            twoCount = twoCount.subtract(oneVal);
        }
        while(contains(5))
        {
            prev = prev.add(digit_place.multiply(fiveVal));
            digit_place= digit_place.multiply(tenVal);
            fiveCount = fiveCount.subtract(oneVal);
        }
        while(contains(4))
        {
            prev = prev.add(digit_place.multiply(fourVal));
            digit_place= digit_place.multiply(tenVal);
            twoCount = twoCount.subtract(twoVal);
        }
        while(contains(3))
        {
            prev = prev.add(digit_place.multiply(threeVal));
            digit_place= digit_place.multiply(tenVal);
            threeCount = threeCount.subtract(oneVal);
        }
        while(contains(2))
        {
            prev = prev.add(digit_place.multiply(twoVal));
            digit_place= digit_place.multiply(tenVal);
            twoCount = twoCount.subtract(oneVal);
        }
        
        if (prev.compareTo(tenVal) == -1 ) 
            prev = prev.add(tenVal);
	
        return prev;
    }
    
    // can we get NUMBER from the parts we have right now?
    boolean contains(int number)
    {
        switch (number)
        {
            case 9:
            if (threeCount.compareTo(twoVal) == -1)
                return false;
            return true;
            case 8:
            if (twoCount.compareTo(threeVal) == -1)
                return false;
            return true;
            case 7:
            if (sevenCount.compareTo(oneVal) == -1)
                return false;
            return true;
            case 6:
            if (twoCount.compareTo(oneVal) == -1 || threeCount.compareTo(oneVal) == -1)
                return false;
            return true;
            case 5:
            if (fiveCount.compareTo(oneVal) == -1)
                return false;
            return true;
            case 4:
            if (twoCount.compareTo(twoVal) == -1)
                return false;
            return true;
            case 3:
            if (threeCount.compareTo(oneVal) == -1)
                return false;
            return true;
            case 2:
            if (twoCount.compareTo(oneVal) == -1)
                return false;
            return true;
            default:
            return false;
        }
    }
    
    // sets the working NUM, gets all the parts, 
    // check if the parts gives the original number and than prints a result
    public void processANumber(BigInteger n)
    {
        setNum(n);
        getParts();
        if(check() || processing.compareTo(BigInteger.valueOf(10)) == -1 )
            System.out.println(createPrevious());
        else
            System.out.println("There is no such number.");// ("+num.toString()+")");
    }
    
    // launch a process for every number we've got in the input (resets counts after each)
    public void run()
    {
        int s = in.size();
        for (int i = 0; i < s; i++) 
        {
	    init();
            processANumber(in.get(i));            
        }
    }
    
    // just creates an instance, reads a data and launches the program
    public static void main(String[] args) 
    {
        Main m = new Main();
        
        m.readInput();
        m.run();
		
        System.exit(0);
    }

    // resets the counters
    private void init()
    {
        twoCount = new BigInteger("0");
        threeCount = new BigInteger("0");
        fiveCount = new BigInteger("0");
        sevenCount = new BigInteger("0");
    }
    
}

[mf]

You can use java.math.BigInteger.

[jumbo]

Thanks for reply.
Good news (for) everyone!

So what about my code? It gives right output for the specified input. But how to test some more...uva toolkit does not contain 10527 problem solver, so it is hard to test this algorithm...

[mf]

The algorithm looks correct to me.

I've noticed a bug in your readInput() procedure: you're using "tmp.intValue() == -1" to test whether a BigInteger tmp is -1. That is not a correct way to do so. What that test does is check that the lowest 32 bits of 2-complement representation of tmp are 1's. This happens when tmp=-1, but also, for example, when tmp=4294967295, 8589934591, ...

Also, you probably shouldn't rely on System.in.available() to return the total size of the input. It could come from a pipe, in which case System.in.available() could return min(size of input, pipe's buffer size, number of bytes written to pipe by the time you make that call).

[jumbo]

Oh, great! Thank you very much for help! I got AC!

It was in the intValue().

It worked even with System.in.available(), I used it in couple of solutions already. I foresee that "bug" can happen with this function, but I tried it and it works so far.

Thanks again!

[ojha]

If there any critical input & output for this problem ???
I'm getting wrong answer ... ...

Code: Select all

import java.math.BigInteger;
import java.util.Scanner;



public class Main {

	public static void main(String[] args) throws Exception{
		Scanner input = new Scanner(System.in);
		while(true){
			
			String string;
			string = input.nextLine();
			
			BigInteger Break = BigInteger.valueOf(-1);
			BigInteger One = BigInteger.valueOf(1);
			
			BigInteger bignumber1 = new BigInteger(string);
			//System.out.println(Break);
			
			if(bignumber1.equals(Break))
				break;
			else{
				int x = bignumber1.intValue();
				if(x < 10)
					System.out.println("1" + x);
				else{
					int [] array = new int[100];
					int count = 0;
					for(int i = 9; i>1; i--){
		            	
		            	BigInteger bignumber2 = BigInteger.valueOf(i);
		                while(true){
		                	BigInteger bignumber3 = bignumber1.mod(bignumber2);
		                	BigInteger zero = BigInteger.ZERO;
		                	if(bignumber3.equals(zero)){
		                		bignumber1 = bignumber1.divide(bignumber2);
		                		array[count++] = i; 
		                		
		                	}
		                	else
		                		break;
		                }
		            }
		            if(bignumber1.equals(One)){
		            	for(int i = count - 1; i>=0; i--)
		            		System.out.print(array[i]);
		            	System.out.println("");
		      
		            }
		            else{
		                System.out.println("There is no such number.");
		            }
			}
			
		}

	}

}
}

[brianfry713]

Input:

Code: Select all

4294967296
-1

Correct output:

Code: Select all

48888888888

[ojha]

Thanks brianfry713, but now getting Run Time Error. Can't make the logic.

Code: Select all

import java.math.BigInteger;
import java.util.Scanner;
import java.io.BufferedReader;


public class main10527 {

	public static void main(String[] args) throws Exception{
		Scanner input = new Scanner(System.in);
		while(true){
			
			String string;
			string = input.nextLine();
			
			BigInteger Break = BigInteger.valueOf(-1);
			BigInteger One = BigInteger.valueOf(1);
			
			BigInteger bignumber1 = new BigInteger(string);
			//System.out.println(Break);
			
			if(bignumber1.equals(Break))
				break;
			else{
				BigInteger Ten = new BigInteger ("10");
				int x = bignumber1.compareTo(Ten);
				if(x < 0)
					System.out.println("1" + bignumber1);
				else{
					int [] array = new int[10];
					int count = 0;
					for(int i = 9; i>1; i--){
		            	
		            	BigInteger bignumber2 = BigInteger.valueOf(i);
		                while(true){
		                	BigInteger bignumber3 = bignumber1.mod(bignumber2);
		                	BigInteger zero = BigInteger.ZERO;
		                	if(bignumber3.equals(zero)){
		                		bignumber1 = bignumber1.divide(bignumber2);
		                		array[count++] = i; 
		                		
		                	}
		                	else
		                		break;
		                }
		            }
		            if(bignumber1.equals(One)){
		            	for(int i = count - 1; i>=0; i--)
		            		System.out.print(array[i]);
		            	System.out.println("");
		      
		            }
		            else{
		                System.out.println("There is no such number.");
		            }
			}
			
		}

	}

}
}

[brianfry713]

Use class Main

[ojha]

Oh sorry, I did use Main when to submit, but got RTE, I guess problem is for different purpose.

[shiam]

Oh sorry, I did use Main when to submit, but got RTE, I guess problem is for different purpose.

Yes, you are absolutely right. You have done some mistakes. Check for this input:

Code: Select all

205891132094649

My AC output is:

Code: Select all

999999999999999

Here your int array size is 10 but the input contains numbers which contains 1000 digits. The desired output will contain more than 1000 digit so you must increase your array size and then check with some larger test case but my suggestion is to use List or vector or some other data structure which dynamically increase their size.
Happy Coding!

[ojha]

Thanks Shiam Vai ... used vector & got AC.