C++, mathematical solution


  • 0
    Z

    Assume k is a good base for n, and n base k has m digits of "1".
    Since the highest bit of n base k is much more significant than other digits, we can approximate k = floor ( m-th root of n ) .
    Then, we only have to traverse m from 2, until k == 1.

    class Solution {
    public:
    	// calculate value of "11...11"
    	static long long sum(long long base, int maxExponent)
    	{
    		long long power = 1;
    		long long value = 0;
    
    		// number of digits = maxExponent + 1
    		for (auto i = 0; i != maxExponent + 1; i++)
    		{
    			value += power;
    			power *= base;
    		}
    
    		return value;
    	}
    	
    	string smallestGoodBase(string n) const {
    		auto min = LLONG_MAX;
    		auto number = stoll(n);
    
    		for (auto maxExponent = 2; ; maxExponent++)
    		{
    			long long base = floor(pow(number, 1.0 / maxExponent));
    
    			if (base == 1)
    			{
    				break;
    			}
    			
    			if (base < min && sum(base, maxExponent) == number)
    			{
    				min = base;
    			}
    		}
    
    		if (min == LLONG_MAX)
    		{
    			return to_string(number - 1);
    		}
    
    		return to_string(min);
    	}
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.