Google foobar challenge
本帖最后由 Seawolf 于 2019-8-13 11:38 编辑继续 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";
}
}
}
页:
[1]