a swift solution 20 line


  • 0

    The math formula is

    n = 1 + k + k^2 + ... + k^(m-1)

    The question is : Given n , find integer value of k and m. There are two ways to solve this :

    1. k = 2 ... n-1, find m
    2. m = 2 ... log2(n) , find k

    It is quite obvious that , we can have a possible O(log(n) ) solution with the second.

    After multiplied by k,

    nk = k + k^2 + ... + k^(m-1) + k^m

    then if the second equation minus the first equation,

    nk - n = k^m - 1

    we can further have ,

    m = pow( nk - n + 1 , 1 / k )

    class Solution {
        func smallestGoodBase(_ n: String) -> String {
            let n = Int64( n )!
            if n < 3 {
                return String( n + 1 )
            }
            let maxm = Int64( ceil(log2(Double(n))) )
            for m in (3...maxm).reversed() {
                let maxk = Int64( ceil (pow( Double( n ), 1 / Double( m - 1 ) ) ))
                for k in max(2, maxk - 1 )...maxk{
                    let m1 =  log( Double( n ) * Double( k - 1 ) + 1  , forBase:   Double(k) )
                    if abs( Double(m) - m1 ) < 0.00000000000001 {
                        return String( k )
                    }
                }
            }
            return String( n - 1 )
        }
    }
    func log( _ val: Double, forBase base: Double) -> Double {
        return log(val)/log(base)
    }

Log in to reply
 

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