Google foobar challenge

Seawolf

Level 3:




起初的想法是用dp来解，但是问题来了，input的数可以最多有309位数字，是一个非常大的数，但是一个array 或者 arraylist  的 limits 是 2^31 - 1， 也就是说根本无法储存，所以要引入BigInteger 类来处理此问题。

Here is the solution：

import java.math.BigInteger;

public class main {

    public static void main(String[] args){

        String x = "13";

        BigInteger leng = new BigInteger(x);

        BigInteger one = new BigInteger("1");

        BigInteger _one = new BigInteger("-1");

//        leng = leng.add(_one);

//        System.out.println(leng.toString(2));

        String test = leng.toString(2);

//        System.out.println(leng.toString(2));
//
//        System.out.println(leng.bitLength());

        int count = 0;

        while(leng.bitLength() !=1){

            int lowestSetbit = leng.getLowestSetBit();

//            System.out.println(check_add(leng.toString(2)));

            if(check_add(leng.toString(2))  && leng.bitLength() != 2){

//                System.out.println(1);

                leng = leng.add(one);

                count = count + 1 ;


            }

            else{

                if(lowestSetbit >= 1){

                    count++;

                    leng = leng.shiftRight(1);

//                    System.out.println(leng.toString(2));
//                    System.out.println(lowestSetbit);

                }
                else{

                    leng = leng.add(_one);

                    count = count + 1;

//                    System.out.println(leng.toString(2));
                }
            }
        }

        System.out.println(count);

//        return count;
    }

    private static boolean check_add(String x){

        boolean need_add = true;

        for(int i = 0 ; i < x.length(); i++){

//            System.out.println(x.substring(i,i+1));

            if(Integer.parseInt(x.substring(i,i+1)) != 1){

//                System.out.println("22222");

                need_add = false;
            }

        }

        return need_add;
    }

}