This is the 18th day of my participation in the Genwen Challenge

The title

For a given integer n, k (k>=2) is said to be a good base of n if all the digits of the k (k>=2) base number of n are 1.

Given n as a string, returns the smallest good base of n as a string.

  • Example 1:

Input: “13” Output: “3” Explanation: The base 3 of 13 is 111.

  • Example 2:

Input: “4681” Output: “8” Explanation: 4681 is 11111 in base 8.

  • Example 3:

Input: “1000000000000000000” Output: “9999999999999999 “Description: the base of 99999999999999 of 1000000000000000000 is 11.

Tip:

  • The range of n is 3, 10 to the 18th.
  • Input is always valid and has no leading 0.

Sum of geometric sequence

If all the digits of the base number k (k>=2) of n are 1, it can be represented as the addition of a geometric sequence

Therefore, according to the sum formula of geometric sequence

Shape:

Since n is in the range of [3, 10^18] and k>=2, according to the monotonicity of the log function, m<60

Binomial theorem

According to the binomial theorem

And because

The combination of the two forms gives

And you end up with k

Their thinking

  1. By summing the geometric sequence, we can quickly get the maximum value of m, thus narrowing our search area

2. According to the value range of M obtained in the previous step, the ergotation was carried out and the conclusion was obtained through the binomial theorem

We can figure out what k is, and then we can see if the current k is n

code

class Solution {
    public String smallestGoodBase(String n) {

        long num = Long.parseLong(n);
        int maxL = (int) Math.floor(Math.log(num) / Math.log(2));
        for (intm=maxL; m>1; m--) {int k = (int) Math.pow(num, 1.0 / m);
            long cur=1,pow=1;
            for(int i=0; i<m; i++) { pow*=k; cur+=pow; }if(cur==num)
                return String.valueOf(k);
        }
        return String.valueOf(num-1); }}Copy the code