Count ways to represent N as sum of powers of 2 | Python3 program for above implementation ; Base Cases ; Check if 2 ^ k can be used as one of the numbers or not ; Otherwise ; Count number of ways to N using 2 ^ k - 1 ; Driver Code
from math import log2 NEW_LINE def numberOfWays ( n , k ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( k == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( n >= pow ( 2 , k ) ) : NEW_LINE INDENT curr_val = pow ( 2 , k ) NEW_LINE return numberOfWays ( n - curr_val , k ) + numberOfWays ( n , k - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return numberOfWays ( n , k - 1 ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE k = log2 ( n ) NEW_LINE print ( numberOfWays ( n , k ) ) NEW_LINE DEDENT