Brute force and binary search


  • 0
    1. O(nlogn), try every base.
        string smallestGoodBase(string n) {
            int64_t num = stoll(n);
            for(int64_t b=2;b<num;b++) {
                int64_t nn = num;
                bool good = 1;
                while(nn) {
                    if(nn%b!=1) {
                        good = 0;
                        break;
                    }
                    nn/=b;
                }
                if(good) return to_string(b);
            }
        }
    
    1. O((logn)^3). There seems to be no obvious way to improve the brute force. So we have to look at the problem in a different way. n is big so it is expensive to try all bases. However, there are only logn all 1s sequence. So we can try each sequence. We can start from the longest all 1s sequence which correponds to the smallest base. For each sequence, we can do binary search to determine if it has a valid base. The idea is from @wgl
        string smallestGoodBase(string n) {
            int64_t num = stoll(n);
            for(int i=log2(num);i>0;i--) {
                int64_t l = 2, r = pow((long double)num,1.0/i);
                while(l<=r) {
                    int64_t mid = l+(r-l)/2;
                    unsigned long long b=1, sum=0;
                    for(int j=0;j<=i;j++,b*=mid) if((sum+=b)>num) break;
                    if(sum == num) return to_string(mid);
                    else if(sum < num) l = mid+1;
                    else r = mid-1;
                }
            }
        }
    
    1. There seems to be better approach using some math derivation. Too lazy to figure it out...

Log in to reply
 

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