Sum of all Perfect Squares lying in the range [ L , R ] for Q queries | Array to precompute the sum of squares from 1 to 100010 so that for every query , the answer can be returned in O ( 1 ) . ; Function to check if a number is a perfect square or not ; Find floating point value of square root of x . ; If square root is an integer ; Function to precompute the perfect squares upto 100000. ; Function to print the sum for each query ; To calculate the precompute function ; Calling the printSum function for every query
var pref = Array ( 100010 ) . fill ( 0 ) ; function isPerfectSquare ( x ) { var sr = Math . sqrt ( x ) ; return ( ( sr - Math . floor ( sr ) ) == 0 ) ? x : 0 ; } function compute ( ) { for ( var i = 1 ; i <= 100000 ; ++ i ) { pref [ i ] = pref [ i - 1 ] + isPerfectSquare ( i ) ; } } function printSum ( L , R ) { var sum = pref [ R ] - pref [ L - 1 ] ; document . write ( sum + " " ) ; } compute ( ) ; var Q = 4 ; arr = [ [ 1 , 10 ] , [ 1 , 100 ] , [ 2 , 25 ] , [ 4 , 50 ] ] ; for ( var i = 0 ; i < Q ; i ++ ) printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ;