3ms, AC, C++, long long int + binary search


  • 20
    W

    The input can be stored in a long long int, here I use unsigned long long int for a larger range. We need to find k, for 1+k^1+k^2+k^3+...+k^d=n. The smallest possible base is k=2, with has the longest possible representation, i.e., largest d. So, to find the smallest base means to find the longest possible representation "11111....1" based on k. As n<=10^18, so n<(1<<62). We iterate the length of the representation from 62 to 2 (2 can always be valid, with base=n-1), and check whether a given length can be valid.

    For a given length d, we use binary search to check whether there is a base k which satisfies 1+k^1+k^2+...k^d=n. The left limit is 1, and the right limit is pow(n,1/d)+1, i.e., the d th square root of n. The code is shown below.

    P.S., I am going to graduate this semester, and need a JOB :)

    class Solution {
    public:
        string smallestGoodBase(string n) {
        unsigned long long tn=(unsigned long long)stoll(n);
        unsigned long long x=1;
        for (int i=62;i>=1;i--) {
            if ((x<<i)<tn) {
                unsigned long long cur=mysolve(tn,i);
                if (cur!=0) return to_string(cur);
            }
        }
        return to_string(tn-1);
        }
        
    unsigned long long mysolve(unsigned long long n,int d) {
        double tn=(double) n;
        unsigned long long right=(unsigned long long)(pow(tn,1.0/d)+1);
        unsigned long long left=1;
        while (left<=right){
            unsigned long long mid=left+(right-left)/2;
            unsigned long long sum=1,cur=1;
            for (int i=1;i<=d;i++) {
                cur*=mid;
                sum+=cur;
            }
            if (sum==n) return mid;
            if (sum>n) right=mid-1;
            else left=mid+1;
        }
        return 0;
    }
    
    };
    

  • 11
    N

    Brilliant idea from you, but i got some improvement here.

    1. Don't need to check the length from 62. For each num, the longest possible length is
      log(num)/log(2)+1

    2. If num = "1111...11" length k under base b,
      num = 1 + b + b^2 + ... + b^(k-1) = (b^k - 1) / (b-1) > b^(k-1)
      There is only one candidate b = pow(num,1.0/(k-1));
      (Not mathematically proven but i couldn't find any counterexample).
      No need to do binary search to find b.

    class Solution {
        typedef unsigned long long ull;
    public:
        string smallestGoodBase(string n) {
            ull num = (ull)stoll(n);
            int maxlen = log(num)/log(2)+1;
            for(int k=maxlen; k>=3; --k){
                ull b = pow(num,1.0/(k-1)), sum = 1, cur = 1;
                for (int i=1; i<k; ++i) 
                    sum += (cur *= b);
                if(sum == num)
                    return to_string(b);
            }  
            return to_string(num-1);
        }
    };
    

  • 0
    M
    This post is deleted!

  • 0
    L

    @niwota : Quote:
    "There is only one candidate b = pow(num,1.0/(k-1));
    (Not mathematically proven but i couldn't find any counterexample).
    No need to do binary search to find b."

    Actually binary search is as fast as using pow(), and can even be faster if you optimize it right (since pow works with floating point, and we only need integer)


  • 0

    @niwota said in 3ms, AC, C++, long long int + binary search:

    (Not mathematically proven but i couldn't find any counterexample).
    No need to do binary search to find b.

    @StefanPochmann in thos post shows that num^1/(k-1) is the only candidate to test. Use the inequality

    • Σp=0:k-1nump ≤ (num+1)k-1.

  • 0

    Correct me if I'm wrong, but the runtime is O(logn * logn * logn). The outer loop is logn then the binary search runs logn times and each search iteration takes logn.

    Also, since our max input is 10^18 we can start our loop at at the largest x that satisfies 2^x < 10^18 which is 59 (62 in the solution above works as well since it is larger than 59)


  • 0

    @KidOptimo said in 3ms, AC, C++, long long int + binary search:

    Correct me if I'm wrong, but the runtime is O(logn * logn * logn). The outer loop is logn then the binary search runs logn times and each search iteration takes logn.

    Also, since our max input is 10^18 we can start our loop at at the largest x that satisfies 2^x < 10^18 which is 59 (62 in the solution above works as well since it is larger than 59)

    Yes, if simply using a trivial bound like left = 1 for binary search, it is O((logN)^3) complexity overall. For more thoughtful way in mysolve, we can achieve O((logN)^2).


  • 0
    M

    @niwota I don't understand where your candidate is from. num = (b^k - 1) / (b-1) > b^(k-1) only proves that pow(num,1.0/(k-1)) > b, right? Could you explain more about it?


  • 0
    N

    @mooc

    We need to check if num equals "1111...11" (length k, k from maxlen to 3) under base b. If the equation exists, num = (b^k - 1)/(b-1) > b^(k-1). We proves that b<pow(num,1.0/(k-1)).

    Because pow function returns a double number but b is usigned long long type, the decimal part of pow(num,1.0/(k-1)) is truncated. That's why i said b <= (unsigned long long)pow(num,1.0/(k-1)) <= pow(num,1.0/(k-1)). b can be any integer no greater than pow(num,1.0/(k-1)). If b is big enough, num = (b^k - 1)/(b-1) is very close to b^(k-1). We can expect that b is almost equal to num^(1/(k-1)).

    @zzg_zzm posted the reference showing that the only candidate is b = (unsigned long long)pow(num,1.0/(k-1)). b is already declared unsigned long long type, thus b=pow(num,1.0/(k-1)) in my code.


  • 0

    @mooc said in 3ms, AC, C++, long long int + binary search:

    @niwota I don't understand where your candidate is from. num = (b^k - 1) / (b-1) > b^(k-1) only proves that pow(num,1.0/(k-1)) > b, right? Could you explain more about it?

    There is another inequality to get the upper bound:

    • (b+1)^(k-1) > 1+b+...+b^(k-1),
      which is easy to see if you use binomial formula to expand the left hand side.

    Therefore, b+1>num^1/(k-1)>b. Note that b is an integer, so b has to be the floor of num^1/(k-1).


  • 0
    A

    why did you add this " if ((x<<d)<t) "?
    I have thought this just narrow the search range. However, If I remove this check, tests fail.


Log in to reply
 

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