# Concise C++ Binary Search solution

• The idea is similar to the other solutions

``````class Solution {
public:
string smallestGoodBase(string n) {
typedef unsigned long long ll;
ll num = stol(n);
for (ll p = log(num+1) / log(2); p >= 2; --p) {
ll lk = 2, rk = pow(num, 1.0 / (p-1))+1;
while (lk <= rk) {
ll mk = lk + (rk - lk) / 2, sum = 0;
for (ll i = 0, f = 1; i < p; ++i, f *= mk)
sum += f;
if (sum < num) lk = mk+1;
else if (sum > num) rk = mk-1;
}
}
}
};``````

``````class Solution {
public:
string smallestGoodBase(string n) {
using ull = unsigned long long;
// num - 1 is the largest possible base
ull num = stoll(n);
// this loop will iterate length from max possible value to min value
// when base == 2, we have longest length of '1'
// 2^0 + 2^1 + ... + 2^(len - 1) == num -> 2^len == num + 1 -> len = log(num + 1) base on 2
// log(num + 1) / log(2) == log (num + 1) base on 2
for (int len = log(num + 1) / log(2); len >= 2; len--) {
// use binary search to find possible base
// b^0 + b^1 + .... + b^(len - 1) == num ->
// b^(len - 1) <= num + 1 ->
// b <= pow(num + 1, 1.0 / (len - 1))
ull l = 2, r = pow(num + 1, 1.0 / (len - 1)) + 1;
while (l < r) {
ull sum = 0, base = l + (r - l) / 2, val = 1;
for (int i = 0; i < len; i++, val *= base)
sum += val;
if (sum == num)