483. Smallest Good Base

Problem

For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.

Now given a string representing n, you should return the smallest good base of n in string format.

Example 1:

Input: "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

Note:

1. The range of n is [3, 10^18].
2. The string representing n is always valid and will not have leading zeros.

Problem Summary

For the given integer n, if all digits of n in base k (k>=2) are 1, then k (k>=2) is called a good base of n.

Given n in string form, return the smallest good base of n in string form.

Hints:

• The range of n is [3, 10^18].
• The input is always valid and has no leading 0.

Solution Approach

• Given a number n, we need to find a base k such that every digit of n in base k is 1. Find the smallest base k.
• This problem is equivalent to finding the smallest positive integer k such that there exists a positive integer m satisfying

{{< katex display >}} \sum_{i=0}^{m} k^{i} = \frac{1-k^{m+1}}{1-k} = n {{< /katex >}}

• This problem requires determining the values of both k and m. m and k are related: once one value is determined, the other is also determined. From

{{< katex display >}} \frac{1-k^{m+1}}{1-k} = n \ {{< /katex >}}

we can get:

{{< katex display >}} m = log_{k}(kn-n+1) - 1 < log_{k}(kn) = 1 + log_{k}n {{< /katex >}}

According to the problem statement, we know k ≥2, m ≥1, so:

{{< katex display >}} 1 \leqslant m \leqslant log_{2}n {{< /katex >}}

Therefore the range of m is determined. The outer loop iterates from 1 to log n. Find the smallest k that can satisfy:

Binary search can be used to approximate and find the smallest k. First find the range of k. From

{{< katex display >}} \frac{1-k^{m+1}}{1-k} = n \ {{< /katex >}}

we can get,

{{< katex display >}} k^{m+1} = nk-n+1 < nk\ \Rightarrow k < \sqrt[m]{n} {{< /katex >}}

So the range of k is [2, n*(1/m) ]. Then use binary search to approximate and find the smallest k, which is the answer.

Code

package leetcode

import (
	"math"
	"math/bits"
	"strconv"
)

func smallestGoodBase(n string) string {
	nVal, _ := strconv.Atoi(n)
	mMax := bits.Len(uint(nVal)) - 1
	for m := mMax; m > 1; m-- {
		k := int(math.Pow(float64(nVal), 1/float64(m)))
		mul, sum := 1, 1
		for i := 0; i < m; i++ {
			mul *= k
			sum += mul
		}
		if sum == nVal {
			return strconv.Itoa(k)
		}
	}
	return strconv.Itoa(nVal - 1)
}