Google foobar challenge

Seawolf

继续 level 3





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

1. import java.math.BigInteger;
   
2. 
   
3. public class main {
   
4. 
   
5.     public static void main(String[] args){
   
6. 
   
7.         String x = "4";
   
8. 
   
9.         String y = "11";
   
10. 
    
11.         BigInteger left = new BigInteger(x);
    
12. 
    
13.         BigInteger right = new BigInteger(y);
    
14. 
    
15.         BigInteger one = new BigInteger("1");
    
16. 
    
17.         int count = 0;
    
18. 
    
19.         while(!(left.compareTo(one) ==0 && right.compareTo(one) == 0)){
    
20. 
    
21.             if (left.compareTo(right) > 0){
    
22. 
    
23.                 left = left.subtract(right);
    
24. 
    
25.                 System.out.println("==============");
    
26. 
    
27.                 System.out.println(left);
    
28. 
    
29.                 count++;
    
30. 
    
31.             }
    
32. 
    
33.             else if (left.compareTo(right) < 0){
    
34. 
    
35.                 right = right.subtract(left);
    
36. 
    
37.                 System.out.println("&&&&&&&&&&&&&&&&&");
    
38. 
    
39.                 System.out.println(right);
    
40. 
    
41.                 count++;
    
42. 
    
43.             }
    
44. 
    
45.             else{
    
46. 
    
47.                 System.out.println("Impossible");
    
48.             }
    
49. 
    
50. 
    
51.         }
    
52. 
    
53.         System.out.println(count);
    
54. 
    
55. 
    
56.     }
    
57. 
    
58. 
    
59. }
    

复制代码

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

Here is the solution：

1. import java.math.BigInteger;
   
2. 
   
3. public class Solution {
   
4. 
   
5.     public static String solution(String x, String y){
   
6. 
   
7. //        String x = "2";
   
8.         //2147483647
   
9. //        String y = "1011111111111111111111111111111111111111111111";
   
10. 
    
11.         BigInteger left = new BigInteger(x);
    
12. 
    
13.         BigInteger right = new BigInteger(y);
    
14. 
    
15.         BigInteger one = new BigInteger("1");
    
16. 
    
17.         BigInteger zero = new BigInteger("0");
    
18. 
    
19.         BigInteger count = new BigInteger("0");
    
20. 
    
21.         if(left.compareTo(right) > 0){
    
22.             BigInteger quo = left.divide(right);
    
23. //            BigInteger result = left.subtract(right);\
    
24.             BigInteger quoTimesRight = quo.multiply(right);
    
25.             if(quo.compareTo(BigInteger.ONE) > 0 &&  quoTimesRight.compareTo(left) != 0){
    
26. 
    
27. //                quoTimesRight = quoTimesRight.subtract(BigInteger.ONE);
    
28.                 count = count.add(quo);
    
29.                 left = left.subtract(quoTimesRight);
    
30. //                System.out.println(left.toString(10));
    
31. //                result = left;
    
32.             }
    
33. 
    
34. 
    
35. //            return result.toString(10);
    
36. 
    
37.         }else if (left.compareTo(right) < 0){
    
38.             BigInteger quo = right.divide(left);
    
39. //            BigInteger result = right.subtract(left);
    
40.             BigInteger quoTimesLeft = quo.multiply(left);
    
41.             if(quo.compareTo(BigInteger.ONE) > 0 &&  quoTimesLeft.compareTo(right) != 0){
    
42. 
    
43. //                quoTimesLeft = quoTimesLeft.subtract(BigInteger.ONE);
    
44.                 count = count.add(quo);
    
45.                 right = right.subtract(quoTimesLeft);
    
46. //                result = right;
    
47. //                System.out.println(right.toString(10));
    
48.             }
    
49. 
    
50. 
    
51. 
    
52. //            return result.toString(10);
    
53.         }
    
54. //            System.out.println("impossible");
    
55. //            return "impossible";
    
56. 
    
57. 
    
58. 
    
59.         if(left.compareTo(one) < 0 || right.compareTo(one) < 0){
    
60. 
    
61. //            System.out.println("impossible");
    
62.             return "impossible";
    
63.         }
    
64. 
    
65.         while(!(left.compareTo(one) == 0 && right.compareTo(one) == 0)){
    
66. 
    
67.             if(left.compareTo(right) == 0){
    
68. 
    
69.                 count = new BigInteger("0");
    
70. 
    
71.                 break;
    
72.             }
    
73. 
    
74.             if (left.compareTo(right) > 0){
    
75. 
    
76.                 left = left.subtract(right);
    
77. 
    
78.                 count = count.add(one);
    
79. 
    
80. //                System.out.println(count.toString(10));
    
81. 
    
82.             }
    
83. 
    
84.             else if (left.compareTo(right) < 0){
    
85. 
    
86.                 right = right.subtract(left);
    
87. 
    
88.                 count = count.add(one);
    
89. 
    
90. //                System.out.println(count.toString(10));
    
91. 
    
92.             }
    
93. 
    
94.             else{
    
95. //                System.out.println("impossibimpossle");
    
96. 
    
97.                 return "impossible";
    
98. 
    
99. //                break;
    
100.             }
     
101. 
     
102. 
     
103.         }
     
104. //        System.out.println(Integer.toString(count));
     
105. 
     
106.         if(count.compareTo(zero) != 0){
     
107. 
     
108. //            System.out.println(count.toString(10));
     
109.             return count.toString(10);
     
110.         }
     
111. 
     
112. 
     
113.         else{
     
114. 
     
115. //            System.out.println("impossible");
     
116.             return "impossible";
     
117.         }
     
118. 
     
119. 
     
120. 
     
121.     }
     
122. 
     
123. }
     

复制代码