Count of numbers whose difference with Fibonacci count upto them is atleast K | Python 3 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
MAX = 1000005 NEW_LINE fibUpto = [ 0 ] * ( MAX + 1 ) NEW_LINE def compute ( sz ) : NEW_LINE INDENT isFib = [ False ] * ( sz + 1 ) NEW_LINE prev = 0 NEW_LINE curr = 1 NEW_LINE isFib [ prev ] = True NEW_LINE isFib [ curr ] = True NEW_LINE while ( curr <= sz ) : NEW_LINE INDENT temp = curr + prev NEW_LINE if ( temp <= sz ) : NEW_LINE INDENT isFib [ temp ] = True NEW_LINE DEDENT prev = curr NEW_LINE curr = temp NEW_LINE DEDENT fibUpto [ 0 ] = 1 NEW_LINE for i in range ( 1 , sz + 1 ) : NEW_LINE INDENT fibUpto [ i ] = fibUpto [ i - 1 ] NEW_LINE if ( isFib [ i ] ) : NEW_LINE INDENT fibUpto [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT def countOfNumbers ( N , K ) : NEW_LINE INDENT compute ( N ) NEW_LINE low , high , ans = 1 , N , 0 NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) >> 1 NEW_LINE if ( mid - fibUpto [ mid ] >= K ) : NEW_LINE INDENT ans = mid NEW_LINE high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT if ( ans ) : NEW_LINE INDENT return ( N - ans + 1 ) NEW_LINE DEDENT return 0 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 10 NEW_LINE K = 3 NEW_LINE print ( countOfNumbers ( N , K ) ) NEW_LINE DEDENT