Smallest Good Base

Problem

Given an integer n as a number, return the smallest base as a string in which n is written as all ones.

For every possible digit count from the binary length down to 2, binary search the base such that 1 + b + ... + b to the k minus 1 equals n; if no base below n works, n itself is the answer. Assume n >= 3.

Hint

With two digits the representation is 1 plus the base, so base n - 1 always works.

Test cases

case 1

in: [13]

expected: "3"

case 2

in: [4681]

expected: "8"

case 3

in: [3]

expected: "2"

case 4

in: [15]

expected: "2"

case 5

in: [1000]

expected: "999"

Starter codePython

def smallest_good_base(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor