Sum of all Perfect Squares lying in the range [ L , R ] for Q queries | Python3 program to find the sum of all perfect squares in the given range ; 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 ; Driver code ; To calculate the precompute function ; Calling the printSum function for every query
from math import sqrt , floor NEW_LINE pref = [ 0 ] * 100010 ; NEW_LINE def isPerfectSquare ( x ) : NEW_LINE INDENT sr = sqrt ( x ) ; NEW_LINE rslt = x if ( sr - floor ( sr ) == 0 ) else 0 ; NEW_LINE return rslt ; NEW_LINE DEDENT def compute ( ) : NEW_LINE INDENT for i in range ( 1 , 100001 ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + isPerfectSquare ( 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 if __name__ == " _ _ main _ _ " : NEW_LINE INDENT compute ( ) ; NEW_LINE Q = 4 ; NEW_LINE arr = [ [ 1 , 10 ] , [ 1 , 100 ] , [ 2 , 25 ] , [ 4 , 50 ] ] ; NEW_LINE for i in range ( Q ) : NEW_LINE INDENT printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; NEW_LINE DEDENT DEDENT