Numbers with a Fibonacci difference between Sum of digits at even and odd positions in a given range | C # 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 ; Initialize dp ; Driver Code ; Generate fibonacci numbers
using System ; using System . Collections . Generic ; public class GFG { static int M = 18 ; static int a , b ; static int [ , , , ] dp = new int [ M , 90 , 90 , 2 ] ; static HashSet < int > fib = new HashSet < int > ( ) ; static void fibonacci ( ) { int prev = 0 , curr = 1 ; fib . Add ( prev ) ; fib . Add ( curr ) ; while ( curr <= 100 ) { int temp = curr + prev ; fib . Add ( temp ) ; prev = curr ; curr = temp ; } } static int count ( int pos , int even , int odd , int tight , List < int > num ) { if ( pos == num . Count ) { if ( num . Count % 2 == 1 ) { odd = odd + even ; even = odd - even ; odd = odd - even ; } int d = even - odd ; if ( fib . Contains ( d ) ) return 1 ; return 0 ; } if ( dp [ pos , even , odd , tight ] != - 1 ) return dp [ pos , even , odd , tight ] ; int ans = 0 ; int limit = ( tight == 1 ? 9 : num [ pos ] ) ; for ( int d = 0 ; d <= limit ; d ++ ) { int currF = tight , currEven = even ; int currOdd = odd ; if ( d < num [ pos ] ) currF = 1 ; if ( pos % 2 == 1 ) currOdd += d ; else currEven += d ; ans += count ( pos + 1 , currEven , currOdd , currF , num ) ; } return dp [ pos , even , odd , tight ] = ans ; } static int solve ( int x ) { List < int > num = new List < int > ( ) ; while ( x > 0 ) { num . Add ( x % 10 ) ; x /= 10 ; } num . Reverse ( ) ; for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < 90 ; j ++ ) { for ( int l = 0 ; l < 90 ; l ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) { dp [ i , j , l , k ] = - 1 ; } } } } return count ( 0 , 0 , 0 , 0 , num ) ; } public static void Main ( String [ ] args ) { fibonacci ( ) ; int L = 1 , R = 50 ; Console . Write ( solve ( R ) - solve ( L - 1 ) + " STRNEWLINE " ) ; L = 50 ; R = 100 ; Console . Write ( solve ( R ) - solve ( L - 1 ) + " STRNEWLINE " ) ; } }