Sum of all Non | 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
var pref = Array ( 100010 ) . fill ( 0 ) ; function isPerfectSquare ( x ) { var s = parseInt ( Math . sqrt ( x ) ) ; return ( s * s == x ) ; } function isNonFibonacci ( n ) { if ( isPerfectSquare ( 5 * n * n + 4 ) || isPerfectSquare ( 5 * n * n - 4 ) ) return 0 ; else return n ; } function compute ( ) { for ( var i = 1 ; i <= 100000 ; ++ i ) { pref [ i ] = pref [ i - 1 ] + isNonFibonacci ( i ) ; } } function printSum ( L , R ) { var sum = pref [ R ] - pref [ L - 1 ] ; document . write ( sum + " " ) ; } compute ( ) ; var Q = 2 ; var arr = [ [ 1 , 5 ] , [ 6 , 10 ] ] ; for ( var i = 0 ; i < Q ; i ++ ) { printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; }