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

• 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);
}
}
}

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;
}

};
``````

• 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)
}
}
};
``````

• This post is deleted!

• @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)

• (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-1`num`p ≤ (`num+1`)k-1.

• 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)

• 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)`.

• @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?

• @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.

• @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).

• 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.

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