5-liner 3ms really TIGHT search bounds with time complexity analysis O((logN)^2) (detailed explanation)


  • 3

    Key Observation: if N in base k >= 2 has all digits as 1's, that means n has representation

    • n = Σp=0:d-1 kp,

    where d is the number of digits in base k. So the problem is equivalent to

    • find smallest k >= 2 such that function f(k,d) := Σp=0:d-1 kp - N = 0 for some integer d.

    As many fellow coders have posted the popular binary search solution for root of f(*, d) with some fixed d, but I think the search bound for d and k should be tightened as much as possible to speed up the algorithm.

    Range of d: Note that f(k,d) is strictly increasing in k, which means f(*,d) has most one root for a fixed d.
    Note that f can be rewritten as

    • f(k,d) = (kd-1)/(k-1)-Nf(2,d) = 2d-1-N,

    so we must have dlog2(N+1) to be able to have a root for f(*,d).

    Range of k: for a fixed d, we have

    • f(k,d) = (kd-1)/(k-1)-N < kd-N,

    so we must have the root k > N1/d.
    We also have

    • f(k,d) = Σp=0:d-1 kp - N > kd-1-N,

    so we must have the root k < N1/(d-1).

    Summary: we loop d only in range [2, log2(N+1)] reversely, and for each d, we binary search root for f(*,d) only in range [N1/d, N1/(d-1)].

        int64_t N; // =stoll(n)
        
        string smallestGoodBase(string n) {
          for (int64_t k, d=log2((N=stoll(n))+1); d>1;) if (k = root(d--)) return to_string(k);
        }
        
        int64_t f(int64_t k, int64_t d) { // f(k,d) = sum k^i - N
          for (int64_t i=0, p=1, sum=1; i<d; sum += p*=k) if (++i == d) return sum-N;
        }
        
        int64_t root(int64_t d) { // binary search root for f(*,d) in range [N^1/d, N^1/(d-1)]
          int64_t m, v, L = pow(N, 1./d), R = pow(N, 1./(d-1));
          for (; L <= R; v<0? L = m+1 : R = m-1) if (!(v = f(m=(L+R)/2,d))) return m;
          return d>2? 0 : N-1;
        }
    

    Time Complexity:

    • The loop in smallestGoodBase has length log N.
    • Apparently, function f(k,d) has O(d) complexity.
    • In binary search root, we have O(d*log(R-L)) = O(d*log R) = O(d*log N1/(d-1)) = O(log N).

    So the overall time complexity is O(log N)2. (N = stoll(n))

    Improvement for Function root:
    Actually, as @StefanPochmann pointed out in this post with binomial theorem, only int64_t k = pow(N, 1./(d-1)) could be the candidate for the root of f(*,d). So method root can be simplified as following:

        int64_t root(int64_t d) { // only N^1/(d-1) could be root for f(*,d)
          int64_t k;
          return d>2? f(k = pow(N,1./(d-1)), d)? 0 : k : N-1;
        }
    

    The overall time complexity still stands as O((log N)^2).


  • 0

    @zzg_zzm Note that I was trying to use solver from Problem 50. Pow(x, n) in f(k,d) to achieve O(log d) complexity instead of the current O(d) complexity, but that involves calculation of k^d instead of k^(d-1), and didn't work probably due to overflow of int64_t. Anyway, d is within O(log N) and this probably won't make much difference.


  • 0
    This post is deleted!

  • 0
    S

    @zzg_zzm Very neat solution and nice explanation. Thank you!


  • 1
    K

    It's 5 lines, but take other 50x times to read your code. readability is very important.

    @zzg_zzm said in 5-liner 3ms really TIGHT search bounds with time complexity analysis O((logN)^2) (detailed explanation):

    string smallestGoodBase(string n) {
    for (int64_t k, d=log2((N=stoll(n))+1); d>1;) if (k = root(d--)) return to_string(k);
    }

    int64_t f(int64_t k, int64_t d) { // f(k,d) = sum k^i - N
      for (int64_t i=0, p=1, sum=1; i<d; sum += p*=k) if (++i == d) return sum-N;
    }
    
    int64_t root(int64_t d) { // binary search root for f(*,d) in range [N^1/d, N^1/(d-1)]
      int64_t m, v, L = pow(N, 1./d), R = pow(N, 1./(d-1));
      for (; L <= R; v<0? L = m+1 : R = m-1) if (!(v = f(m=(L+R)/2,d))) return m;
      return d>2? 0 : N-1;
    }

Log in to reply
 

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