Sum of all Non | Java 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 ; Driver Code ; Pre - computation ; Loop to find the sum for each query
import java . util . * ; class GFG { static long pref [ ] = new long [ 100010 ] ; static boolean isPerfectSquare ( int x ) { int s = ( int ) Math . sqrt ( x ) ; return ( s * s == x ) ; } static int isNonFibonacci ( int n ) { if ( isPerfectSquare ( 5 * n * n + 4 ) || isPerfectSquare ( 5 * n * n - 4 ) ) return 0 ; else return n ; } static void compute ( ) { for ( int i = 1 ; i <= 100000 ; ++ i ) { pref [ i ] = pref [ i - 1 ] + isNonFibonacci ( i ) ; } } static void printSum ( int L , int R ) { int sum = ( int ) ( pref [ R ] - pref [ L - 1 ] ) ; System . out . print ( sum + " ▁ " ) ; } public static void main ( String [ ] args ) { compute ( ) ; int Q = 2 ; int arr [ ] [ ] = { { 1 , 5 } , { 6 , 10 } } ; for ( int i = 0 ; i < Q ; i ++ ) { printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; } } }