483. Smallest Good Base

HardMathBinary Search
Leetcode Link

Problem Description

The LeetCode problem is asking us to find the smallest good base for a given integer n that is represented as a string. A good base k for n means that if we were to write n in base k, all its digits would be 1's. For example, the number 7 in base 2 is written as 111, so 2 is a good base for 7. The challenge is to find the smallest such base, which is always greater than or equal to 2.

Intuition

To approach this problem, the key observation is that n can be expressed as a sum of geometric series when using a base k in which all digits are 1's.

Mathematically, for a base k and m digits in base k representation, n can be expressed as:

n = 1 + k^1 + k^2 + ... + k^(m-1)

This is a geometric series, and we need to find the smallest k (good base) for which there is some m that satisfies the equation.

Since n consists entirely of 1's for a good base k, the larger the base k, the fewer digits m we'll need, and vice versa. This means that for larger m, k will be smaller.

The maximum m is bounded due to the size of n — n's binary representation is the longest m could be since binary (base 2) has the most 1's for any given number. Therefore, the loop counter m starts from 63 (since a 64-bit integer has a maximum of 63 1's plus 1 sign bit).

The solution works by iterating over possible values of m from this maximum m down to 2. For each m, it performs a binary search to find the smallest k such that the sum of the geometric series equals n. Once we find such k, we return it as the result. If we fail to find such k for all m, then the smallest good base is n-1 (because the only representation of n with all 1's using base n-1 is 11).

To speed up the process, the cal(k, m) function is defined to calculate the sum of the geometric series efficiently. This avoids recalculating powers of k multiple times.

The binary search is conducted within the range of [2, num - 1] for each m. Whenever the cal(mid, m) function, which represents the sum of the series for base mid and m digits, yields a value less than num (our original number), we know that the base is too small and needs to be larger; thus, we adjust our search range accordingly.

The solution, therefore, combines the understanding of geometric series with binary search to find the smallest good base within an optimized time complexity.

Learn more about Math and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The solution involves the implementation of an iterative approach combined with binary search. Let's go through the steps and the algorithm utilized:

  1. Convert the input string n to an integer num to perform numerical operations.

  2. Loop through m starting from 63 down to 2. This represents the possible lengths of the number n when written in base k, all in 1's. The number 63 is used because for a 64-bit integer, the maximum length of pure 1's (excluding the sign bit) is 63.

  3. For each value of m, perform a binary search to find the smallest base k that satisfies the condition that all digits of n base k are 1's. Set the initial search range with l (left) as 2 and r (right) as num - 1, indicating the minimum and maximum potential bases, respectively.

  4. Conduct the binary search:

    • Compute the middle point mid between l and r as (l + r) >> 1, where >> 1 is a bitwise right shift equivalent to division by 2.
    • Calculate the sum of the geometric series using cal(mid, m).
      • The cal function takes a base k and a length m, iteratively multiplies the base (geometric progression), and accumulates the result in s, initializing with 1 (for the first digit, which is always 1).
    • Check if the computed series sum is greater than or equal to num. If so, update r to mid, indicating that the current base may be too large, or the right range from mid to r does not contain the smallest base.
    • Otherwise, update the left range boundary l to mid + 1, as the current base mid is too small to represent num with all 1's.
    • This process narrows down the search space until the left and right boundaries converge.

  5. After the binary search loop concludes, the function checks if the value discovered at l produces a sum equal to num using cal(l, m). If it does, this base l is the smallest good base for the given m, and it is returned as a string.

  6. If no suitable base k is found across all m values in the loop, which means n cannot be written as all 1's in any other base than itself minus 1, the function returns num - 1 as a string. This corresponds to the base n-1 since any number n in base n-1 is 11.

The solution makes efficient use of binary search within an iterative loop to significantly narrow down the possible candidates for a good base and arrive at the smallest possible one. It leverages the mathematical properties of geometric series for verification within the binary search.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's assume n is given as the string "13". First, we convert this string to an integer num = 13 to perform arithmetic operations.

Starting with m equal to 63 and decreasing, we're looking for the smallest base k such that 13 can be written as a series of 1's – this would take too long computationally, though, so for the sake of the example, let's consider smaller m values. We will start with m = 3, as larger values of m would result in smaller values of k, and we are searching for the smallest k.

When m = 3, our equation n = 1 + k^1 + k^2 should equal 13. So in this step, we'll perform a binary search between 2 and 12 (num - 1) to find the smallest k.

During each iteration of the binary search, we:

  1. Find mid. For the first iteration, l is 2, r is 12, so mid will be (2 + 12) >> 1 which equals 7.
  2. Calculate cal(mid, m). Using mid = 7, we find that cal(7, 3) = 1 + 7 + 49 = 57.
  3. Since 57 is greater than 13, mid is too large. We adjust our range and set r to mid - 1, which is now 6.
  4. Find the new mid, which is now (2 + 6) >> 1 which equals 4.
  5. Calculating cal(4, 3) gives us 1 + 4 + 16 = 21, which is again greater than 13, so we adjust r again to mid - 1, now 3.
  6. New mid is (2 + 3) >> 1 which equals 2.
  7. Calculate cal(2, 3) giving us 1 + 2 + 4 = 7, which is less than 13, so we adjust l to mid + 1, now 3.
  8. Since l now equals r, the search concludes.

We find that using k = 3, cal(3, 3) equals 1 + 3 + 9 = 13, which matches our num. Therefore, base k = 3 can represent the number 13 as 111 in base 3, and given this is the smallest k we've found, we return k = 3 as the smallest good base for the number 13.

1
2For the given integer `n` of value "13" (which we convert to the integer `num = 13` for processing), we aim to find the smallest base `k` such that `13` is all `1's` in that base.
3
4We start with `m = 3`, a possible length of the all `1's` representation (i.e., `111`):
5
61. Conduct a binary search for `k` between `2` and `12`.
7    - First iteration: `mid = 7`. Calculate `cal(7, 3) = 57`. This is greater than `13`, so set `r` to `6`.
8    - Second iteration: `mid = 4`. Calculate `cal(4, 3) = 21`. Still greater than `13`, set `r` to `3`.
9    - Third iteration: `mid = 2`. Calculate `cal(2, 3) = 7`. Less than `13`, set `l` to `3`.
102. When `l` and `r` converge, we find that `cal(3, 3)` equals `13`.
113. Return base `k = 3` as the smallest good base, which represents `13` as `111` in this base.

Solution Implementation

1class Solution:
2    def smallestGoodBase(self, n: str) -> str:
3        # Helper function to calculate the sum of a geometric series
4        def calculate_sum(base, term_count):
5            power_product = sum_product = 1
6            for i in range(term_count):
7                power_product *= base
8                sum_product += power_product
9            return sum_product
10
11        # Convert input string to integer
12        num = int(n)
13        # Try to find the smallest base by iterating from the largest term count down to 2
14        for term_count in range(63, 1, -1):
15            # Binary search for the good base
16            left, right = 2, num - 1
17            while left < right:
18                mid = (left + right) // 2
19                if calculate_sum(mid, term_count) >= num:
20                    right = mid
21                else:
22                    left = mid + 1
23            # Check if we found the exact sum that matches the given number
24            if calculate_sum(left, term_count) == num:
25                return str(left)
26        # If no good base is found, return num - 1, 
27        # which is always a good base (n = k^1 + 1)
28        return str(num - 1)
29
1class Solution {
2    // Finds the smallest base for a number with the properties of a good base
3    public String smallestGoodBase(String n) {
4        long num = Long.parseLong(n); // Convert string to long integer
5      
6        // loop to check all possible lengths starting from the highest possible
7        for (int length = 63; length >= 2; --length) {
8            long base = getBaseForGivenLength(length, num);
9            if (base != -1) {
10                return String.valueOf(base); // if a valid base is found, return it
11            }
12        }
13        // If no good base is found, return n-1 as base as per the mathematical property
14        return String.valueOf(num - 1);
15    }
16
17    // Helper method to get a base for a given range and target number
18    private long getBaseForGivenLength(int length, long targetNumber) {
19        long left = 2, right = targetNumber - 1;
20        while (left < right) { // Binary search to find the good base
21            long mid = (left + right) >>> 1; // Use unsigned right shift for division by 2
22            long result = calculatePowerSum(mid, length);
23          
24            if (result >= targetNumber) {
25                right = mid; // Adjust right boundary
26            } else {
27                left = mid + 1; // Adjust left boundary
28            }
29        }
30        return calculatePowerSum(right, length) == targetNumber ? right : -1;
31    }
32
33    // Helper method to calculate the sum of powers for a given base and length
34    private long calculatePowerSum(long base, int length) {
35        long power = 1; // Start with k^0
36        long sum = 0;
37      
38        for (int i = 0; i < length; ++i) {
39            if (Long.MAX_VALUE - sum < power) {
40                return Long.MAX_VALUE;
41            }
42            sum += power; // Add current power of base to sum
43          
44            // Check if next multiplication would cause overflow
45            if (Long.MAX_VALUE / power < base) {
46                power = Long.MAX_VALUE;
47            } else {
48                power *= base; // Otherwise, multiply power by base
49            }
50        }
51        return sum;
52    }
53}
54
1class Solution {
2public:
3    // Function to find the smallest good base of a number as a string
4    string smallestGoodBase(string n) {
5        // Convert the input number n to a long integer
6        long value = stol(n);
7      
8        // Calculate the maximum possible value of m, assuming base 2 (binary)
9        int maxM = floor(log(value) / log(2));
10      
11        // Start iterating from the largest possible m to 1
12        for (int m = maxM; m > 1; --m) {
13            // Calculate the base k for the current m using nth root
14            int base = pow(value, 1.0 / m);
15          
16            // Initialize multiplier (mul) and sum (s) for geometric progression
17            long mul = 1, sum = 1;
18
19            // Calculate the sum of the sequence with m terms
20            for (int i = 0; i < m; ++i) {
21                mul *= base; // multiply by base each time
22                sum += mul;  // add the term to the sum
23            }
24
25            // If sum equals to the value, we've found the smallest good base
26            if (sum == value) {
27                return to_string(base);
28            }
29        }
30      
31        // If no other base found, the smallest good base is value - 1
32        // since a K-base number system of K+1 (here v) would always be written as 10...0 (which equals K+1).
33        return to_string(value - 1);
34    }
35};
36
1// Import the required function from JavaScript Math object
2import { log10, pow, floor } from 'math';
3
4// Function to find the smallest good base for a number given as a string
5function smallestGoodBase(n: string): string {
6    // Convert the input string to a number
7    let value: number = parseInt(n);
8  
9    // Calculate the maximum possible value of m assuming the base is 2 (binary) system
10    let maxM: number = floor(log10(value) / log10(2));
11  
12    // Iterate from the largest possible value of m to 1
13    for (let m = maxM; m > 1; m--) {
14        // Calculate the base (k) for the current value of m using the nth root
15        let base: number = pow(value, 1.0 / m);
16      
17        // Initialize variables for the geometric progression
18        let mul: number = 1; // Multiplier
19        let sum: number = 1; // Sum of the geometric sequence
20      
21        // Calculate the sum of the sequence with m terms
22        for (let i = 0; i < m; i++) {
23            mul *= base; // Multiply by the base for each term
24            sum += mul;  // Add the computed term to the sum
25        }
26      
27        // If the sum is equal to the original number, we've found the smallest good base
28        if (sum === value) {
29            return base.toString();
30        }
31    }
32  
33    // If no base was found, return value - 1, which is always a good base for any number
34    return (value - 1).toString();
35}
36
37// Please note the usage of 'log10' instead of 'log' in TypeScript.
38// TypeScript uses the built-in JavaScript Math object's log10 method for base 10 logarithms.
39
Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is determined by the nested loop:

  1. The outer loop runs for each possible value of m, which ranges from 63 to 2, resulting in a maximum of 62 iterations. This is because m represents the maximum length of digits in base k representation for the number n, and since the largest number in this context is 2^64 - 1, the maximum length of m is 63.

  2. The inner loop is a binary search, which runs in O(log(n)) time, where n is the given number. In each iteration of this binary search, the function cal is called which performs, at maximum, m multiplications.

Given that m is at most 63, and for each m we perform a binary search which takes O(log(n)) time, the overall time complexity of the inner loop is O(m * log(num)).

  1. The cal function itself runs in O(m) time, since it contains a loop that iterates m times.

Combining these aspects together, the total time complexity of the code is O(m * m * log(num)) or, more concretely, O(63 * log(num)) because m is a constant at most 63.

Space Complexity

The space complexity of the algorithm is O(1):

  1. The space used by the algorithm is constant, as there are only a few integer variables being used and no additional space (like data structures) that grow with the size of the input.

  2. The cal function uses a constant amount of space as well, as the variables p and s are just integers and do not require space that scales with the input size.

Hence, there is no significant space usage that scales with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫