Sum of all Non | Python3 implementation to find the sum of all non - fibonacci numbers in a range from L to R ; Array to precompute the sum of non - fibonacci numbers ; Function to find if a number is a perfect square ; Function that returns N if N is non - fibonacci number ; N is Fibinacci if one of 5 * n * n + 4 or 5 * n * n - 4 or both are perferct square ; Function to precompute sum of non - fibonacci Numbers ; Function to find the sum of all non - fibonacci numbers in a range ; Pre - computation ; Loop to find the sum for each query
from math import sqrt NEW_LINE pref = [ 0 ] * 100010 NEW_LINE def isPerfectSquare ( x ) : NEW_LINE INDENT s = int ( sqrt ( x ) ) NEW_LINE if ( s * s == x ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def isNonFibonacci ( n ) : NEW_LINE INDENT x = 5 * n * n NEW_LINE if ( isPerfectSquare ( x + 4 ) or isPerfectSquare ( x - 4 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return n NEW_LINE DEDENT DEDENT def compute ( ) : NEW_LINE INDENT for i in range ( 1 , 100001 ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + isNonFibonacci ( i ) NEW_LINE DEDENT DEDENT def printSum ( L , R ) : NEW_LINE INDENT sum = pref [ R ] - pref [ L - 1 ] NEW_LINE print ( sum , end = " ▁ " ) NEW_LINE DEDENT compute ( ) NEW_LINE Q = 2 NEW_LINE arr = [ [ 1 , 5 ] , [ 6 , 10 ] ] NEW_LINE for i in range ( Q ) : NEW_LINE INDENT printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) NEW_LINE DEDENT