Count numbers which can be constructed using two numbers | Returns count of numbers from 1 to n that can be formed using x and y . ; Create an auxiliary array and initialize it as false . An entry arr [ i ] = True is going to mean that i can be formed using x and y ; x and y can be formed using x and y . ; Initialize result ; Traverse all numbers and increment result if a number can be formed using x and y . ; If i can be formed using x and y ; Then i + x and i + y can also be formed using x and y . ; Increment result ; Driver code
def countNums ( n , x , y ) : NEW_LINE INDENT arr = [ False for i in range ( n + 2 ) ] NEW_LINE if ( x <= n ) : NEW_LINE INDENT arr [ x ] = True NEW_LINE DEDENT if ( y <= n ) : NEW_LINE INDENT arr [ y ] = True NEW_LINE DEDENT result = 0 NEW_LINE for i in range ( min ( x , y ) , n + 1 ) : NEW_LINE INDENT if ( arr [ i ] ) : NEW_LINE INDENT if ( i + x <= n ) : NEW_LINE INDENT arr [ i + x ] = True NEW_LINE DEDENT if ( i + y <= n ) : NEW_LINE INDENT arr [ i + y ] = True NEW_LINE DEDENT result = result + 1 NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT n = 15 NEW_LINE x = 5 NEW_LINE y = 7 NEW_LINE print ( countNums ( n , x , y ) ) NEW_LINE