package com.fishercoder.solutions;

import java.math.BigInteger;

/**
 * 483. Smallest Good Base
 *
 * For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.

 Now given a string representing n, you should return the smallest good base of n in string format.

 Example 1:
 Input: "13"
 Output: "3"
 Explanation: 13 base 3 is 111.

 Example 2:
 Input: "4681"
 Output: "8"
 Explanation: 4681 base 8 is 11111.

 Example 3:
 Input: "1000000000000000000"
 Output: "999999999999999999"
 Explanation: 1000000000000000000 base 999999999999999999 is 11.

 Note:
 The range of n is [3, 10^18].
 The string representing n is always valid and will not have leading zeros.

 */
public class _483 {

    /**credit: https://discuss.leetcode.com/topic/82130/java-solution-with-hand-writing-explain*/
    public String smallestGoodBase(String n) {
        long nn = Long.parseLong(n);
        long res = 0;
        for (int k = 60; k >= 2; k--) {
            long start = 2;
            long end = nn;
            while (start < end) {
                long m = start + (end - start) / 2;

                BigInteger left = BigInteger.valueOf(m);
                left = left.pow(k).subtract(BigInteger.ONE);
                BigInteger right = BigInteger.valueOf(nn).multiply(BigInteger.valueOf(m).subtract(BigInteger.ONE));
                int cmr = left.compareTo(right);
                if (cmr == 0) {
                    res = m;
                    break;
                } else if (cmr < 0) {
                    start = m + 1;
                } else {
                    end = m;
                }
            }

            if (res != 0) {
                break;
            }
        }

        return "" + res;
    }

}

@@ -710,19 +710,71 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 credit: 
@@ -853,19 +853,33 @@
 -explain
-*/%0A
+%0A         */%0A    
     publ
@@ -921,24 +921,28 @@
 ) %7B%0A        
+ 
+   
 long nn = Lo
@@ -962,24 +962,28 @@
 n);%0A        
+    
 long res = 0
@@ -984,16 +984,20 @@
 es = 0;%0A
+    
         
@@ -1036,24 +1036,28 @@
             
+    
 long start =
@@ -1068,24 +1068,28 @@
             
+    
 long end = n
@@ -1103,16 +1103,20 @@
         
+   
+ 
 while (s
@@ -1125,24 +1125,28 @@
 rt %3C end) %7B%0A
+    
             
@@ -1194,32 +1194,36 @@
                 
+ 
+   
 BigInteger left 
@@ -1263,16 +1263,20 @@
         
+  
+  
 left = l
@@ -1312,16 +1312,20 @@
 r.ONE);%0A
+    
         
@@ -1448,16 +1448,20 @@
         
+    
 int cmr 
@@ -1497,24 +1497,28 @@
             
+ 
+   
 if (cmr == 0
@@ -1541,16 +1541,20 @@
         
+    
 res = m;
@@ -1550,24 +1550,28 @@
    res = m;%0A
+    
             
@@ -1597,24 +1597,28 @@
             
+    
 %7D else if (c
@@ -1647,16 +1647,20 @@
         
+    
 start = 
@@ -1678,24 +1678,28 @@
             
+   
+ 
 %7D else %7B%0A   
@@ -1695,16 +1695,20 @@
  else %7B%0A
+    
         
@@ -1736,34 +1736,40 @@
                 
-%7D%0A
+    %7D%0A  
             %7D%0A%0A 
@@ -1756,35 +1756,41 @@
 %7D%0A              
+  
 %7D%0A%0A
+    
             if (
@@ -1809,32 +1809,36 @@
                 
+    
 break;%0A         
@@ -1840,26 +1840,33 @@
         
+ 
-%7D%0A
+   %7D%0A   
         
 %7D%0A%0A     
@@ -1857,27 +1857,30 @@
         
+ 
 %7D%0A
-%0A
+   
         
 return %22
@@ -1871,16 +1871,17 @@
         
+ 
 return %22
@@ -1889,16 +1889,26 @@
  + res;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 483