Last updated on July 21st, 2024 at 04:31 am

Here, We see Smallest Good Base LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Binary Search, Math

Companies

Google

Level of Question

Hard

Smallest Good Base LeetCode Solution

Problem Statement

Given an integer n represented as a string, return the smallest good base of n.

We call k >= 2 a good base of n, if all digits of n base k are 1‘s.

Example 1:
Input: n = “13”
Output: “3”
Explanation: 13 base 3 is 111.

Example 2:
Input: n = “4681”
Output: “8”
Explanation: 4681 base 8 is 11111.

Example 3:
Input: n = “1000000000000000000”
Output: “999999999999999999”
Explanation: 1000000000000000000 base 999999999999999999 is 11.

1. Smallest Good Base Leetcode Solution C++

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;
                else return to_string(mk);
            }
        }
        return to_string(num-1);
    }
};

2. Smallest Good Base Leetcode Solution Java

class Solution {
    public String smallestGoodBase(String n) {
        long tn = Long.parseLong(n);
        long x = 1; 
        for (int i = 62; i >= 1; i--) {
            if ((x << i) < tn) {
                long cur = mySolve(tn, i);
                if (cur != 0) {
                    return Long.toString(cur);
                }
            }
        } 
        return Long.toString(tn - 1);
    }
    
    private long mySolve(long n, int d) {
        double tn = (double) n;
        long right = (long) (Math.pow(tn, 1.0 / d) + 1);
        long left = 1;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            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;
    }
}

3. Smallest Good Base Leetcode Solution JavaScript

var smallestGoodBase = function (n) {
    n = BigInt(n);
    let compute = (base, len) => (base ** BigInt(len) - 1n) / (base - 1n);
    for (let len = BigInt(Math.floor(Math.log2(Number(n))) + 1); len >= 2n; len--) {
        let low = 2n, high = n;
        while (low <= high) {
            let mid = (low + high) / 2n;
            let sum = compute(mid, len);
            if (sum === n) {
                return mid.toString();
            } else if (sum < n) {
                low = mid + 1n;
            } else {
                high = mid - 1n;
            }
        }
    }
    return (n - 1n).toString();
};

4. Smallest Good Base Leetcode Solution Python

class Solution(object):
    def smallestGoodBase(self, n):
        s=1
        ans = []
        n = int(n)
        while(s<65):
            l=2
            h=10**18
            res = -1
            while(l<=h):
                mid=(l+h)//2
                p = (mid**s - 1)//(mid-1) 
                if p == n:
                    res = mid
                    h = mid - 1
                else:
                    if p>n:
                        h = mid - 1
                    else:
                        l = mid + 1
            if res!=-1:
                ans.append(res)
            s+=1
        return str(min(ans))