Google foobar challenge

Seawolf

Level 3:




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

Here is the solution：

1. import java.math.BigInteger;
   
2. 
   
3. public class main {
   
4. 
   
5.     public static void main(String[] args){
   
6. 
   
7.         String x = "13";
   
8. 
   
9.         BigInteger leng = new BigInteger(x);
   
10. 
    
11.         BigInteger one = new BigInteger("1");
    
12. 
    
13.         BigInteger _one = new BigInteger("-1");
    
14. 
    
15. //        leng = leng.add(_one);
    
16. 
    
17. //        System.out.println(leng.toString(2));
    
18. 
    
19.         String test = leng.toString(2);
    
20. 
    
21. //        System.out.println(leng.toString(2));
    
22. //
    
23. //        System.out.println(leng.bitLength());
    
24. 
    
25.         int count = 0;
    
26. 
    
27.         while(leng.bitLength() !=1){
    
28. 
    
29.             int lowestSetbit = leng.getLowestSetBit();
    
30. 
    
31. //            System.out.println(check_add(leng.toString(2)));
    
32. 
    
33.             if(check_add(leng.toString(2))  && leng.bitLength() != 2){
    
34. 
    
35. //                System.out.println(1);
    
36. 
    
37.                 leng = leng.add(one);
    
38. 
    
39.                 count = count + 1 ;
    
40. 
    
41. 
    
42.             }
    
43. 
    
44.             else{
    
45. 
    
46.                 if(lowestSetbit >= 1){
    
47. 
    
48.                     count++;
    
49. 
    
50.                     leng = leng.shiftRight(1);
    
51. 
    
52. //                    System.out.println(leng.toString(2));
    
53. //                    System.out.println(lowestSetbit);
    
54. 
    
55.                 }
    
56.                 else{
    
57. 
    
58.                     leng = leng.add(_one);
    
59. 
    
60.                     count = count + 1;
    
61. 
    
62. //                    System.out.println(leng.toString(2));
    
63.                 }
    
64.             }
    
65.         }
    
66. 
    
67.         System.out.println(count);
    
68. 
    
69. //        return count;
    
70.     }
    
71. 
    
72.     private static boolean check_add(String x){
    
73. 
    
74.         boolean need_add = true;
    
75. 
    
76.         for(int i = 0 ; i < x.length(); i++){
    
77. 
    
78. //            System.out.println(x.substring(i,i+1));
    
79. 
    
80.             if(Integer.parseInt(x.substring(i,i+1)) != 1){
    
81. 
    
82. //                System.out.println("22222");
    
83. 
    
84.                 need_add = false;
    
85.             }
    
86. 
    
87.         }
    
88. 
    
89.         return need_add;
    
90.     }
    
91. 
    
92. }
    

复制代码