Leetcode -483- Minimum good base

[Blog link]

A path to learning at 🐔

The nuggets home page

[B].

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" Description: The base 3 of 13 is 111. Example 2: Input: "4681" Output: "8" Description: The base 8 of 4681 is 11111. Example 3: Input: "1000000000000000000" Output: "9999999999999999 "Description: the base of 9999999999999999 of 1000000000000000000 is 11. Hint: n ranges from [3, 10^18]. Input is always valid and has no leading 0. Related Topics Math Binary Search 👍 65 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: sum formula of geometric sequence


  • S n = a 1 – a n q 1 – q S_n=\dfrac{a_1-a_nq}{1-q}     (Q is the common ratio and n is the number of 1s after s is converted to base Q.)
  • The larger n is, the smaller q is. The maximum value of n is **(s-1)**
  • Because s must be a good base format to convert to s minus one which is 11
  • Because it’s the least good base
  • So you can start with the minimum common ratio and iterate through the range **[2,s-1]** identified as the common ratio
  • So let’s start with I = 2 and let’s push out S *(i-1)+1
  • So the way to determine tempT’s maximum is called TLE
public String smallestGoodBase(String s) {
            long target = Long.parseLong(s);
            for (long i = 2; i < target; i++) {
                long tempT = target * (i - 1) + 1;
                // exclude the I case that is not satisfied
                if(tempT % i ! =0) {
                    continue;
                }
                TempT is tempT I to the NTH power
                while (tempT % i == 0&& tempT ! = i) { tempT /= i; }if (tempT == i) {
                    returnString.valueOf(i); }}return String.valueOf(target - 1);
        }
Copy the code

Time complexity O(n*logn)

Train number two: Train number one: Pull down the inequality

  • Idea one is sure there’s a solution

  • t e m p T = i n < s ∗ i tempT = i^n<s*i

  • n < l o g i s + 1 < 60 n<log_i^s + 1<60
  • Then according to the binomial theorem (the official solution can be derived from I = nm \ SQRT [m]{n}mn down-line integer)

  • Enumerates the number of I satisfying the condition starting from the maximum value of n, and the first encountered is the minimum value of k (n identifies the base number of I).
public String smallestGoodBase(String s) {
            long nVal = Long.parseLong(s);
            int mMax = (int) Math.floor(Math.log(nVal) / Math.log(2));
            for (int n = mMax; n > 1; n--) {
                int i = (int) Math.pow(nVal, 1.0 / n);
                long mul = 1, sum = 1;
                for (int t = 0; t < n; t++) {
                    mul *= i;
                    sum += mul;
                }
                if (sum == nVal) {
                    returnInteger.toString(i); }}return Long.toString(nVal - 1);
        }
Copy the code

Time complexity (O(
l o g 2 n ∗ l o g 2 n log_2^n*log_2^n ))