Leetcode Problem 483. Smallest Good Base

483. Smallest Good Base

Leetcode Solutions

Binary Search for Smallest Good Base

  1. Convert the input string n to an integer num.
  2. Calculate the maximum possible length of a good base representation for num using math.floor(math.log(num, 2)) + 1.
  3. Loop through all possible lengths k in decreasing order from max_len down to 2.
  4. For each k, set the search range for the base m to be between 2 and num - 1.
  5. Use binary search to find the smallest good base m for the current k.
  6. Calculate s, the sum of k 1's in base m.
  7. If s is equal to num, return m as a string.
  8. If s is less than num, update the left bound of the search range to mid + 1.
  9. If s is greater than num, update the right bound of the search range to mid - 1.
  10. If no good base is found for any k, return num - 1 as a string.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...