Count of subarrays having product as a perfect cube | Java program for the above approach ; Function to store the prime factorization of a number ; If N is divisible by i ; Increment v [ i ] by 1 and calculate it modulo by 3 ; Divide the number by i ; If the number is not equal to 1 ; Increment v [ n ] by 1 ; Calculate it modulo 3 ; Function to count the number of subarrays whose product is a perfect cube ; Store the required result ; Stores the prime factors modulo 3 ; Stores the occurrences of the prime factors ; Traverse the array , arr [ ] ; Store the prime factors and update the vector v ; Update the answer ; Increment current state of the prime factors by 1 ; Print the result ; Driver Code
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static int MAX = ( int ) ( 1e5 ) ; static class Key { int arr [ ] ; Key ( int arr [ ] ) { this . arr = arr ; } @ Override public int hashCode ( ) { return 31 + Arrays . hashCode ( arr ) ; } @ Override public boolean equals ( Object obj ) { if ( this == obj ) return true ; if ( obj == null || ( getClass ( ) != obj . getClass ( ) ) ) return false ; Key other = ( Key ) obj ; if ( ! Arrays . equals ( arr , other . arr ) ) return false ; return true ; } } static void primeFactors ( int v [ ] , int n ) { for ( int i = 2 ; i * i <= n ; i ++ ) { while ( n % i == 0 ) { v [ i ] ++ ; v [ i ] %= 3 ; n /= i ; } } if ( n != 1 ) { v [ n ] ++ ; v [ n ] %= 3 ; } } static void countSubarrays ( int arr [ ] , int n ) { int ans = 0 ; int v [ ] = new int [ MAX ] ; HashMap < Key , Integer > mp = new HashMap < > ( ) ; mp . put ( new Key ( v ) , 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { primeFactors ( v , arr [ i ] ) ; ans += mp . getOrDefault ( new Key ( v ) , 0 ) ; Key vv = new Key ( v ) ; mp . put ( vv , mp . getOrDefault ( vv , 0 ) + 1 ) ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 8 , 4 , 2 } ; int N = arr . length ; countSubarrays ( arr , N ) ; } }