Smallest number greater than n that can be represented as a sum of distinct power of k | Function to find the smallest number greater than or equal to n represented as the sum of distinct powers of k ; Vector P to store the base k representation of the number ; If the representation is >= 2 , then this power of k has to be added once again and then increase the next power of k and make the current power 0 ; Reduce all the lower power of k to 0 ; Check if the most significant bit also satisfy the above conditions ; Converting back from the k - nary representation to decimal form . ; Driver code
def greaterK ( n , k ) : NEW_LINE INDENT index = 0 NEW_LINE p = [ 0 for i in range ( n + 2 ) ] NEW_LINE x = n NEW_LINE while ( x > 0 ) : NEW_LINE INDENT p [ index ] = x % k NEW_LINE x //= k NEW_LINE index += 1 NEW_LINE DEDENT idx = 0 NEW_LINE for i in range ( 0 , len ( p ) - 1 , 1 ) : NEW_LINE INDENT if ( p [ i ] >= 2 ) : NEW_LINE INDENT p [ i ] = 0 NEW_LINE p [ i + 1 ] += 1 NEW_LINE for j in range ( idx , i , 1 ) : NEW_LINE INDENT p [ j ] = 0 NEW_LINE DEDENT idx = i + 1 NEW_LINE DEDENT if ( p [ i ] == k ) : NEW_LINE INDENT p [ i ] = 0 NEW_LINE p [ i + 1 ] += 1 NEW_LINE DEDENT DEDENT j = len ( p ) - 1 NEW_LINE if ( p [ j ] >= 2 ) : NEW_LINE INDENT p [ index ] = 1 NEW_LINE index += 1 NEW_LINE DEDENT ans = 0 NEW_LINE i = len ( p ) - 1 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT ans = ans * k + p [ i ] NEW_LINE i -= 1 NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 29 NEW_LINE k = 7 NEW_LINE greaterK ( n , k ) NEW_LINE DEDENT