@@ -0,0 +1,1375 @@
+package test;%0A%0A/*%0Ascala%3E test.Test.multiply(39998, 39999)%0Ares17: Int = 1599880002%0A%0Ascala%3E test.Test.multiply2(39998, 39999)%0Ares18: Int = 1599880002%0A%0Ascala%3E test.Test.multiply3(39998, 39999)%0Ares19: Int = 1599880002%0A*/%0A%0Apublic class Test %7B%0A  public static int multiply(int a, int b) %7B%0A    int bigger = a %3C b ? b : a;%0A    int smaller = a %3C b ? a : b;%0A    int product = 0;%0A    while (smaller %3E 0) %7B%0A      product += bigger;%0A      smaller--;%0A    %7D%0A    return product;%0A  %7D%0A%0A  public static int multiply2(int a, int b) %7B%0A    int bigger = a %3C b ? b : a;%0A    int smaller = a %3C b ? a : b;%0A    int product = 0;%0A    int i = 0;%0A    while (smaller %3E 0) %7B%0A      if ((smaller & 1) == 1) %7B%0A        product += bigger %3C%3C i;%0A      %7D%0A      i++;%0A      smaller %3E%3E= 1;%0A    %7D%0A    return product;%0A  %7D%0A%0A  // Solution from CTCI, runs in O(log s), where s is a smaller of two numbers%0A  public static int multiply3(int a, int b) %7B%0A    int bigger = a %3C b ? b : a;%0A    int smaller = a %3C b ? a : b;%0A    return minProductHelper(smaller, bigger);%0A  %7D%0A%0A  private static int minProductHelper(int smaller, int bigger) %7B%0A    if (smaller == 0) return 0;%0A    else if (smaller == 1) return bigger;%0A    int s = smaller %3E%3E 1; // divide by 2%0A    int halfProd = minProductHelper(s, bigger);%0A    if (smaller %25 2 == 0) %7B%0A      return halfProd + halfProd;%0A    %7D else %7B%0A      return halfProd + halfProd + bigger;%0A    %7D%0A  %7D%0A%7D%0A

add multiply solution