Google foobar challenge

Seawolf

继续 level 3





因为number的大小 could be 10^50, so we still need big integer.

import java.math.BigInteger;

public class main {

    public static void main(String[] args){

        String x = "4";

        String y = "11";

        BigInteger left = new BigInteger(x);

        BigInteger right = new BigInteger(y);

        BigInteger one = new BigInteger("1");

        int count = 0;

        while(!(left.compareTo(one) ==0 && right.compareTo(one) == 0)){

            if (left.compareTo(right) > 0){

                left = left.subtract(right);

                System.out.println("==============");

                System.out.println(left);

                count++;

            }

            else if (left.compareTo(right) < 0){

                right = right.subtract(left);

                System.out.println("&&&&&&&&&&&&&&&&&");

                System.out.println(right);

                count++;

            }

            else{

                System.out.println("Impossible");
            }


        }

        System.out.println(count);


    }


}

这个code有问题，当一个数特别大，另一个数特别小的时候，会消耗很多的时间，因为每次只从那个较大的数减去较小的数，系统会run out of time and finally it will fail
所以怎么办呢，要相处一个办法来处理两个相差很大的数

Here is the solution：

import java.math.BigInteger;

public class Solution {

    public static String solution(String x, String y){

//        String x = "2";
        //2147483647
//        String y = "1011111111111111111111111111111111111111111111";

        BigInteger left = new BigInteger(x);

        BigInteger right = new BigInteger(y);

        BigInteger one = new BigInteger("1");

        BigInteger zero = new BigInteger("0");

        BigInteger count = new BigInteger("0");

        if(left.compareTo(right) > 0){
            BigInteger quo = left.divide(right);
//            BigInteger result = left.subtract(right);\
            BigInteger quoTimesRight = quo.multiply(right);
            if(quo.compareTo(BigInteger.ONE) > 0 &&  quoTimesRight.compareTo(left) != 0){

//                quoTimesRight = quoTimesRight.subtract(BigInteger.ONE);
                count = count.add(quo);
                left = left.subtract(quoTimesRight);
//                System.out.println(left.toString(10));
//                result = left;
            }


//            return result.toString(10);

        }else if (left.compareTo(right) < 0){
            BigInteger quo = right.divide(left);
//            BigInteger result = right.subtract(left);
            BigInteger quoTimesLeft = quo.multiply(left);
            if(quo.compareTo(BigInteger.ONE) > 0 &&  quoTimesLeft.compareTo(right) != 0){

//                quoTimesLeft = quoTimesLeft.subtract(BigInteger.ONE);
                count = count.add(quo);
                right = right.subtract(quoTimesLeft);
//                result = right;
//                System.out.println(right.toString(10));
            }



//            return result.toString(10);
        }
//            System.out.println("impossible");
//            return "impossible";



        if(left.compareTo(one) < 0 || right.compareTo(one) < 0){

//            System.out.println("impossible");
            return "impossible";
        }

        while(!(left.compareTo(one) == 0 && right.compareTo(one) == 0)){

            if(left.compareTo(right) == 0){

                count = new BigInteger("0");

                break;
            }

            if (left.compareTo(right) > 0){

                left = left.subtract(right);

                count = count.add(one);

//                System.out.println(count.toString(10));

            }

            else if (left.compareTo(right) < 0){

                right = right.subtract(left);

                count = count.add(one);

//                System.out.println(count.toString(10));

            }

            else{
//                System.out.println("impossibimpossle");

                return "impossible";

//                break;
            }


        }
//        System.out.println(Integer.toString(count));

        if(count.compareTo(zero) != 0){

//            System.out.println(count.toString(10));
            return count.toString(10);
        }


        else{

//            System.out.println("impossible");
            return "impossible";
        }



    }

}