Numbers with a Fibonacci difference between Sum of digits at even and odd positions in a given range | Java 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
import java . util . * ; class GFG { static int M = 18 ; static int a , b ; static int [ ] [ ] [ ] [ ] dp = new int [ M ] [ 90 ] [ 90 ] [ 2 ] ; static HashSet < Integer > fib = new HashSet < Integer > ( ) ; 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 , Vector < Integer > num ) { if ( pos == num . size ( ) ) { if ( num . size ( ) % 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 . get ( pos ) ) ; for ( int d = 0 ; d <= limit ; d ++ ) { int currF = tight , currEven = even ; int currOdd = odd ; if ( d < num . get ( 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 ) { Vector < Integer > num = new Vector < Integer > ( ) ; while ( x > 0 ) { num . add ( x % 10 ) ; x /= 10 ; } Collections . reverse ( num ) ; 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 ; System . out . print ( solve ( R ) - solve ( L - 1 ) + "NEW_LINE"); L = 50 ; R = 100 ; System . out . print ( solve ( R ) - solve ( L - 1 ) + "NEW_LINE"); } }