Java O((logn)^2) binary search solution


  • 3
    F

    To begin with, the whole problem is equivalent to solving the following equation with smallest k (assuming k >= 2 and m >= 1):

    f(k, m) = n

    where k is the base of the numbers, m is the number of digit 1's in this base, f(k, m) = 1 + k + k^2 + ... + k^(m-1) = (k^m - 1)/(k-1) is the numeric value of the number in base 10, and n is the numeric value of the given input string in base 10.

    Before we jump into solutions of the equation, let's first dig up some properties of the function f(k, m) = (k^m - 1)/(k-1).

    1. If m is fixed, f(k, m) is monotonically increasing on k.
    2. If k is fixed, f(k, m) is also monotonically increasing on m.

    Now suppose we have two different solutions for the above equation: (k1, m1) and (k2, m2). Without loss of generality, let's assume m1 > m2, then we can show k1 < k2 as follows: n = f(k2, m2) = f(k1, m1) > f(k1, m2) ==> k2 > k1. Similarly for the other case: m1 < m2 ==> k1 > k2. Therefore k and m will be inversely related provided the equation is held true.

    The conclusion above suggests that if we can simply find a solution to the equation f(k, m) = n with the largest possible m, then the corresponding k is guaranteed to be the smallest. So now we need to figure out the upper and lower limit on m to impose constraint on our searching range. (Strictly speaking, we may also proceed in the other way round, i.e., to find the smallest k directly but that turns out to be O(n).)

    Note that if the equation is held true, smaller k will correspond to larger m. Since the minimum of k is 2, we know the maximum of m will be log(n + 1) (logarithm of (n+1) in base 2). What about the lower limit? Note that n >= 3, therefore m cannot be 1 (otherwise the numeric value would be 1 and the equation will have no solutions). To summarize, we have: 2 <= m <= log(n + 1).

    So our solution will go like this, starting from the upper limit of m, check if we can find a k so that the equation f(k, m) = n is held true. If so, return the corresponding k as the solution. Otherwise decrease the value of m by 1 and repeat the process until either a solution is found or all values of m have been exhausted. Note that for any n >= 3, there is a trivial solution where k = n - 1 and m = 2, therefore our searching process above is guaranteed to find at least one solution.

    The last part is how to find the solution to the equation with m fixed. A straightforward way would be doing binary search. One point worth noting here is the upper and lower limits for the searching range of k. For the upper limit, note that n = f(k, m) = 1 + k + ... + k^(m-1) > k^(m-1) ==> k < n^(1/(m-1)). For the lower limit, note that n = f(k, m) = (k^m - 1)/(k-1) <= (k^m - 1) ==> k >= (n+1)^(1/m). To summarize: (n+1)^(1/m) <= k <= n^(1/(m-1)).

    So here comes our final solution based on the analyses above. Note that the range of the input n is [3, 10^18], so n can fit into a long type variable. Also if for each m, k is in the searching range specified above, we won't have overflow problem. As for the time complexity, in the worst case, we need to scan the whole range of m, which is O(logn); for each m, the binary search is O(logn) too; therefore our solution will run at O((logn)^2).

    public String smallestGoodBase(String n) {
        long num = Long.valueOf(n);
            
        for (int m = (int)(Math.log(num + 1) / Math.log(2)); m >= 2; m--) {
            long l = (long)(Math.pow(num + 1, 1.0 / m));
            long r = (long)(Math.pow(num, 1.0 / (m - 1)));
            	
            while (l <= r) {
                long k = l + ((r - l) >> 1);
                long f = 0L;
                for (int i = 0; i < m; i++, f = f * k + 1);
            		
                if (num == f) {
            	return String.valueOf(k);
                } else if (num < f) {
            	r = k - 1;
                } else {
            	l = k + 1;
                }
            }
        }
            
        return String.valueOf(num - 1);
    }
    

  • 0
    H

    @fun4LeetCode
    Could you please explain why the maximum of m will be log(n + 1)?


  • 0
    F

    @hyj143 Hi hyj143. As I said, smaller k corresponds to larger m. Since the minimum value of k is 2, the corresponding value of m will be a maximum. Now if k = 2, the function f(k, m) will become: f(k, m) = (k^m - 1)/(k-1) = (2^m - 1)/(2-1) = 2^m - 1. If the equation is held true, this should be equal to the numeric value of the input string, which is n. Therefore we have: 2^m - 1 = n, which leads to the maximum value of m as log(n + 1)(logarithm of (n+1) in base 2).


  • 0
    H

    @fun4LeetCode

    Thanks, I wasn't sure where the "plus one" come from. This is a very good math prove.


  • 0
    D

    @fun4LeetCode Nice solution. Some thoughts.

    1. There is a typo in your explanation: it is k that is within [(n+1)^(1/m), n^(1/(m-1))) instead of m.

    2. When you have the base k, and the digits m, I understand your way of calculating f(k,m). But I have tried another way, which doesn't work. I just use (long)((Math.pow(k, m)-1)/(k-1)). Why is this wrong? numerical error?

    3. Your loop already handles the case m==2, but why do you still need to return String.valueOf(num -1) at the end of the function?

    4. I have once thought a solution that begins with base. For each base, we do binary search. Because we can imagine there is a 2D matrix, first dimension is base, second dimension is digits. One good property about this matrix is that along each dimension, it is always increasing. My solution is O(nlglgn). So your idea is one step further and deeper than my thought.


  • 0
    F

    @dachuan.huang Hi dachuan.huang. Thanks for the feedback.

    1. Nice catch. Typo corrected.
    2. You are right. Take a look at this stackoverflow post
    3. The final return statement is just a dummy statement required by java method.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.