Count of numbers whose difference with Fibonacci count upto them is atleast K | Java program to find the count of numbers whose difference with Fibonacci count upto them is atleast K ; fibUpto [ i ] denotes the count of fibonacci numbers upto i ; Function to compute all the Fibonacci numbers and update fibUpto array ; Store the first two Fibonacci numbers ; Compute the Fibonacci numbers and store them in isFib array ; Compute fibUpto array ; Function to return the count of valid numbers ; Compute fibUpto array ; Binary search to find the minimum number that follows the condition ; Check if the number is valid , try to reduce it ; Ans is the minimum valid number ; Driver Code
import java . util . * ; class GFG { static int MAX = 1000005 ; static int [ ] fibUpto = new int [ MAX + 1 ] ; static void compute ( int sz ) { boolean [ ] isFib = new boolean [ sz + 1 ] ; int prev = 0 , curr = 1 ; isFib [ prev ] = isFib [ curr ] = true ; while ( curr <= sz ) { int temp = curr + prev ; if ( temp <= sz ) isFib [ temp ] = true ; prev = curr ; curr = temp ; } fibUpto [ 0 ] = 1 ; for ( int i = 1 ; i <= sz ; i ++ ) { fibUpto [ i ] = fibUpto [ i - 1 ] ; if ( isFib [ i ] ) fibUpto [ i ] ++ ; } } static int countOfNumbers ( int N , int K ) { compute ( N ) ; int low = 1 , high = N , ans = 0 ; while ( low <= high ) { int mid = ( low + high ) >> 1 ; if ( mid - fibUpto [ mid ] >= K ) { ans = mid ; high = mid - 1 ; } else low = mid + 1 ; } return ( ans > 0 ? N - ans + 1 : 0 ) ; } public static void main ( String [ ] args ) { int N = 10 , K = 3 ; System . out . print ( countOfNumbers ( N , K ) ) ; } }