Numbers with a Fibonacci difference between Sum of digits at even and odd positions in a given range | Python3 program to count the numbers in the range having the difference between the sum of digits at even and odd positions as a Fibonacci Number ; To store all the Fibonacci numbers ; Function to generate Fibonacci numbers upto 100 ; Adding the first two Fibonacci numbers in the set ; Computing the remaining Fibonacci numbers using the first two Fibonacci numbers ; Function to return the count of required numbers from 0 to num ; Base Case ; Check if the difference is equal to any fibonacci number ; If this result is already computed simply return it ; Maximum limit upto which we can place digit . If tight is 1 , means number has already become smaller so we can place any digit , otherwise num [ pos ] ; If the current position is odd add it to currOdd , otherwise to currEven ; Function to convert x into its digit vector and uses count ( ) function to return the required count ; Driver Code ; Generate fibonacci numbers
M = 18 NEW_LINE a = 0 NEW_LINE b = 0 NEW_LINE dp = [ [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 90 ) ] for k in range ( 90 ) ] for l in range ( M ) ] NEW_LINE fib = set ( ) NEW_LINE def fibonacci ( ) : NEW_LINE INDENT prev = 0 NEW_LINE curr = 1 NEW_LINE fib . add ( prev ) NEW_LINE fib . add ( curr ) NEW_LINE while ( curr <= 100 ) : NEW_LINE INDENT temp = curr + prev NEW_LINE fib . add ( temp ) NEW_LINE prev = curr NEW_LINE curr = temp NEW_LINE DEDENT DEDENT def count ( pos , even , odd , tight , num ) : NEW_LINE INDENT if ( pos == len ( num ) ) : NEW_LINE INDENT if ( ( len ( num ) & 1 ) ) : NEW_LINE INDENT val = odd NEW_LINE odd = even NEW_LINE even = val NEW_LINE DEDENT d = even - odd NEW_LINE if ( d in fib ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if ( dp [ pos ] [ even ] [ odd ] [ tight ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ even ] [ odd ] [ tight ] NEW_LINE DEDENT ans = 0 NEW_LINE if ( tight == 1 ) : NEW_LINE INDENT limit = 9 NEW_LINE DEDENT else : NEW_LINE INDENT limit = num [ pos ] NEW_LINE DEDENT for d in range ( limit ) : NEW_LINE INDENT currF = tight NEW_LINE currEven = even NEW_LINE currOdd = odd NEW_LINE if ( d < num [ pos ] ) : NEW_LINE INDENT currF = 1 NEW_LINE DEDENT if ( pos & 1 ) : NEW_LINE INDENT currOdd += d NEW_LINE DEDENT else : NEW_LINE INDENT currEven += d NEW_LINE DEDENT ans += count ( pos + 1 , currEven , currOdd , currF , num ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def solve ( x ) : NEW_LINE INDENT num = [ ] NEW_LINE while ( x > 0 ) : NEW_LINE INDENT num . append ( x % 10 ) NEW_LINE x //= 10 NEW_LINE DEDENT num = num [ : : - 1 ] NEW_LINE return count ( 0 , 0 , 0 , 0 , num ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT fibonacci ( ) NEW_LINE L = 1 NEW_LINE R = 50 NEW_LINE print ( solve ( R ) - solve ( L - 1 ) + 1 ) NEW_LINE L = 50 NEW_LINE R = 100 NEW_LINE print ( solve ( R ) - solve ( L - 1 ) + 2 ) NEW_LINE DEDENT