Count of elements having odd number of divisors in index range [ L , R ] for Q queries | Function count the number of elements having odd number of divisors ; Initialise dp [ ] array ; Precomputation ; Find the Prefix Sum ; Iterate for each query ; Find the answer for each query ; Driver Code ; Given array arr [ ] ; Given Query ; Function Call
function OddDivisorsCount ( n , q , a , Query ) { var DP = new Array ( n ) . fill ( 0 ) ; for ( var i = 0 ; i < n ; i ++ ) { var x = Math . sqrt ( a [ i ] ) ; if ( x * x == a [ i ] ) DP [ i ] = 1 ; } for ( var i = 1 ; i < n ; i ++ ) { DP [ i ] = DP [ i - 1 ] + DP [ i ] ; } var l , r ; for ( var i = 0 ; i < q ; i ++ ) { l = Query [ i ] [ 0 ] ; r = Query [ i ] [ 1 ] ; if ( l == 0 ) { document . write ( DP [ r ] + " " ) ; } else { document . write ( DP [ r ] - DP [ l - 1 ] + " " ) ; } } } var N = 5 ; var Q = 3 ; var arr = [ 2 , 4 , 5 , 6 , 9 ] ; var Query = [ [ 0 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] ] ; OddDivisorsCount ( N , Q , arr , Query ) ;