Count of elements having odd number of divisors in index range [ L , R ] for Q queries | Java program for the above approach ; 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void OddDivisorsCount ( int n , int q , int a [ ] , pair [ ] Query ) { int DP [ ] = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { int x = ( int ) Math . sqrt ( a [ i ] ) ; if ( x * x == a [ i ] ) DP [ i ] = 1 ; } for ( int i = 1 ; i < n ; i ++ ) { DP [ i ] = DP [ i - 1 ] + DP [ i ] ; } int l , r ; for ( int i = 0 ; i < q ; i ++ ) { l = Query [ i ] . first ; r = Query [ i ] . second ; if ( l == 0 ) { System . out . print ( DP [ r ] + "NEW_LINE"); } else { System . out . print ( DP [ r ] - DP [ l - 1 ] + "NEW_LINE"); } } } public static void main ( String [ ] args ) { int N = 5 ; int Q = 3 ; int arr [ ] = { 2 , 4 , 5 , 6 , 9 } ; pair [ ] Query = { new pair ( 0 , 2 ) , new pair ( 1 , 3 ) , new pair ( 1 , 4 ) } ; OddDivisorsCount ( N , Q , arr , Query ) ; } }