Smallest good base

Math Binary Search

45.5% acceptance

Jan 13, 2026

426

540

Given an integer n represented as a string, return the smallest good base of n. We call k >= 2 a good base of n, if all digits of n base k are 1's.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_good_base(n: String) -> String {
    let n_val = n.parse::<u64>().unwrap();
    
    // For each possible number of digits m (from max to 2)
    // n = k^0 + k^1 + ... + k^(m-1) = (k^m - 1) / (k - 1)
    for m in (2..=64).rev() {
      // Binary search for k
      let mut left = 2_u64;
      let mut right = ((n_val as f64).powf(1.0 / (m - 1) as f64) as u64) + 1;
      
      while left <= right {
        let k = left + (right - left) / 2;
        let mut sum = 0_u64;
        let mut valid = true;
        
        // Calculate k^0 + k^1 + ... + k^(m-1)
        for i in 0..m {
          if let Some(new_sum) = sum.checked_add(k.saturating_pow(i as u32)) {
            sum = new_sum;
            if sum > n_val {
              valid = false;
              break;
            }
          } else {
            valid = false;
            break;
          }
        }
        
        if valid && sum == n_val {
          return k.to_string();
        } else if !valid || sum > n_val {
          right = k - 1;
        } else {
          left = k + 1;
        }
      }
    }
    
    (n_val - 1).to_string()
  }
}