Smallest Good Base - Practice Coding Problems

Smallest Good Base - Problem

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.

In other words, n represented in base k should be 111...1 (all ones).

Input & Output

Example 1 — Basic Case

$ Input: n = "13"

› Output: "3"

💡 Note: 13 in base 3 is 111: 1×3² + 1×3¹ + 1×3⁰ = 9 + 3 + 1 = 13. Base 2 gives 1101 (not all 1s), so 3 is the smallest good base.

Example 2 — Small Number

$ Input: n = "4"

› Output: "3"

💡 Note: 4 in base 3 is 11: 1×3¹ + 1×3⁰ = 3 + 1 = 4. Base 2 gives 100 (not all 1s), so 3 is the smallest good base.

Example 3 — Edge Case

$ Input: n = "2"

› Output: "2" would be invalid, but smallest good base is actually base n-1 = "1" which is invalid. By definition, we return n-1 when no valid base ≥ 2 exists, but 2 in base 1 would be "11" conceptually.

Constraints

n is represented as a string
3 ≤ n ≤ 10¹⁸
n does not have leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

Given n = 13 (decimal)

Process

Find smallest base k where n = 111...1 in base k

Output

Base 3: 13 = 111₃ = 1×9 + 1×3 + 1×1

Key Takeaway

🎯 Key Insight: Use geometric series formula n = (k^m - 1)/(k - 1) to find the base mathematically

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is using the geometric series formula: for m digits of all 1's, n = (k^m - 1)/(k - 1). Best approach is mathematical formula with binary search on digit count. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n log n)	O(log n)	Try every base from 2 to n-1 and check if n can be represented as all 1's
Mathematical Formula	O(log n)	O(1)	Use geometric series formula and precise mathematical calculations
Binary Search on Answer	O(log² n)	O(1)	Binary search on the number of digits, then solve for the base using geometric series

Brute Force — Algorithm Steps

Iterate through all bases k from 2 to n-1
For each k, convert n to base k
Check if resulting representation contains only 1's
Return first k that satisfies the condition

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with base k=2

Check

Convert n to base k, verify all digits are 1

Result

Return first valid base found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* n) {
    long long num = atoll(n);
    static char result[32];
    
    if (num == 1) {
        strcpy(result, "2");
        return result;
    }
    
    for (long long k = 2; k < num; k++) {
        long long temp = num;
        while (temp > 0) {
            if (temp % k != 1) break;
            temp /= k;
        }
        if (temp == 0) {
            sprintf(result, "%lld", k);
            return result;
        }
    }
    
    sprintf(result, "%lld", num - 1);
    return result;
}

int main() {
    char n[32];
    fgets(n, sizeof(n), stdin);
    n[strcspn(n, "\n")] = 0;
    char* result = solution(n);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Try up to n bases, each conversion takes O(log n) time

⚡ Linearithmic

Space Complexity

O(log n)

Space needed to store digits during base conversion

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler