Given an array arr[] consisting of N positive integers, the task is to count the number of subarrays with product of its elements equal to a perfect cube.
Examples:
Input: arr[] = {1, 8, 4, 2}
Output: 6
Explanation:
The subarrays with product of elements equal to a perfect cube are:
- {1}. Therefore, product of subarray = 1 (= (1)3).
- {1, 8}. Therefore, product of subarray = 8 ( = 23).
- {8}. Therefore, product of subarray = 8 = (23).
- {4, 2}. Therefore, product of subarray = 8 (= 23).
- {8, 4, 2}. Therefore, product of subarray = 64 (= 43).
- {1, 8, 4, 2}. Therefore, product of subarray = 64 (= 43).
Therefore, the total count is 6.
Input: arr[] = {10, 10,10}
Output: 1
Naive Approach: The simplest approach is to generate all possible subarrays from the given array and count those subarrays whose product of subarray elements is a perfect cube. After checking for all the subarrays, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to check if a number// is perfect cube or notbool perfectCube(int N){Â Â Â Â int cube_root;Â
    // Find the cube_root    cube_root = (int)round(pow(N, 1.0 / 3.0));Â
    // If cube of cube_root is    // same as N, then return true    if (cube_root * cube_root * cube_root == N) {        return true;    }Â
    // Otherwise    return false;}Â
// Function to count subarrays// whose product is a perfect cubevoid countSubarrays(int a[], int n){    // Store the required result    int ans = 0;Â
    // Traverse all the subarrays    for (int i = 0; i < n; i++) {        int prod = 1;        for (int j = i; j < n; j++) {Â
            prod = prod * a[j];Â
            // If product of the current            // subarray is a perfect cube            if (perfectCube(prod))Â
                // Increment count                ans++;        }    }Â
    // Print the result    cout << ans;}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { 1, 8, 4, 2 };Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]);Â
    countSubarrays(arr, N);Â
    return 0;} |
Java
import java.util.*;public class GFG{Â Â public static void main(String args[])Â Â {Â Â Â Â int arr[] = { 1, 8, 4, 2 };Â Â Â Â int N = arr.length;Â Â Â Â countSubarrays(arr, N);Â Â }Â
  // Function to count subarrays  // whose product is a perfect cube  static void countSubarrays(int a[], int n)  {         // Store the required result    int ans = 0;Â
    // Traverse all the subarrays    for (int i = 0; i < n; i++)     {      int prod = 1;      for (int j = i; j < n; j++)       {Â
        prod = prod * a[j];Â
        // If product of the current        // subarray is a perfect cube        if (perfectCube(prod))Â
          // Increment count          ans++;      }    }Â
    // Print the result    System.out.println(ans);  }Â
  // Function to check if a number  // is perfect cube or not  static boolean perfectCube(int N)  {    int cube_root;Â
    // Find the cube_root    cube_root = (int)Math.round(Math.pow(N, 1.0 / 3.0));Â
    // If cube of cube_root is    // same as N, then return true    if (cube_root * cube_root * cube_root == N)     {      return true;    }Â
    // Otherwise    return false;  }}Â
// This code is contributed by abhinavjain194. |
Python3
# Python 3 program for the above approachÂ
# Function to check if a number# is perfect cube or notdef perfectCube(N):Â
    # Find the cube_root    cube_root = round(pow(N, 1 / 3))Â
    # If cube of cube_root is    # same as N, then return true    if (cube_root * cube_root * cube_root == N):        return TrueÂ
    # Otherwise    return FalseÂ
# Function to count subarrays# whose product is a perfect cubedef countSubarrays(a, n):Â
    # Store the required result    ans = 0Â
    # Traverse all the subarrays    for i in range(n):        prod = 1        for j in range(i, n):Â
            prod = prod * a[j]Â
            # If product of the current            # subarray is a perfect cube            if (perfectCube(prod)):Â
                # Increment count                ans += 1Â
    # Print the result    print(ans)Â
# Driver Codeif __name__ == "__main__":Â
    arr = [1, 8, 4, 2]    N = len(arr)Â
    countSubarrays(arr, N)Â
    # This code is contributed by ukasp. |
C#
// C# program to implement// the above approachusing System;public class GFG{Â
// Driver Codepublic static void Main(String[] args){Â Â Â Â int[] arr = { 1, 8, 4, 2 };Â Â Â Â int N = arr.Length;Â Â Â Â countSubarrays(arr, N);}Â
  // Function to count subarrays  // whose product is a perfect cube  static void countSubarrays(int[] a, int n)  {         // Store the required result    int ans = 0;Â
    // Traverse all the subarrays    for (int i = 0; i < n; i++)     {      int prod = 1;      for (int j = i; j < n; j++)       {Â
        prod = prod * a[j];Â
        // If product of the current        // subarray is a perfect cube        if (perfectCube(prod))Â
          // Increment count          ans++;      }    }Â
    // Print the result    Console.Write(ans);  }Â
  // Function to check if a number  // is perfect cube or not  static bool perfectCube(int N)  {    int cube_root;Â
    // Find the cube_root    cube_root = (int)Math.Round(Math.Pow(N, 1.0 / 3.0));Â
    // If cube of cube_root is    // same as N, then return true    if (cube_root * cube_root * cube_root == N)     {      return true;    }Â
    // Otherwise    return false;  }}Â
// This code is contributed by souravghosh0416. |
Javascript
<script>  // Function to count subarrays  // whose product is a perfect cube  function countSubarrays(a , n)  {         // Store the required result    var ans = 0;Â
    // Traverse all the subarrays    for (i = 0; i < n; i++)     {      var prod = 1;      for (j = i; j < n; j++)       {Â
        prod = prod * a[j];Â
        // If product of the current        // subarray is a perfect cube        if (perfectCube(prod))Â
          // Increment count          ans++;      }    }Â
    // Print the result    document.write(ans);  }Â
  // Function to check if a number  // is perfect cube or not  function perfectCube(N)  {    var cube_root;Â
    // Find the cube_root    cube_root = parseInt(Math.round(Math.pow(N, 1.0 / 3.0)));Â
    // If cube of cube_root is    // same as N, then return true    if (cube_root * cube_root * cube_root == N)     {      return true;    }Â
    // Otherwise    return false;  }Â
  var arr = [ 1, 8, 4, 2 ];  var N = arr.length;  countSubarrays(arr, N);Â
// This code is contributed by 29AjayKumar </script> |
6
Â
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by storing the number of prime factors modulo 3 in a HashMap while traversing the array and count perfect cubes accordingly. Follow the steps below to solve the problem:Â
- Initialize a variable, say ans, to store the required result, and an array V with 0s to store the frequency of prime factors mod 3 for every element in the given array arr[].
- Initialize a Hashmap, say M, to store the frequency of the current state of prime factors and increment V by 1 in the HashMap.
- Traverse the array arr[] using the variable i perform the following steps:
- Store the frequency of prime factors mod 3 of arr[i] in V.
- Increment the value of ans by frequency of V in M and then increment the value of V in M.
- After completing the above steps. print the value of ans as the result.
Below is the implementation of the above approach:Â
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAX 1e5Â
// Function to store the prime// factorization of a numbervoid primeFactors(vector<int>& v, int n){Â Â Â Â for (int i = 2; i * i <= n; i++) {Â
        // If N is divisible by i        while (n % i == 0) {Â
            // Increment v[i] by 1 and            // calculate it modulo by 3            v[i]++;            v[i] %= 3;Â
            // Divide the number by i            n /= i;        }    }Â
    // If the number is not equal to 1    if (n != 1) {Â
        // Increment v[n] by 1        v[n]++;Â
        // Calculate it modulo 3        v[n] %= 3;    }}Â
// Function to count the number of// subarrays whose product is a perfect cubevoid countSubarrays(int arr[], int n){    // Store the required result    int ans = 0;Â
    // Stores the prime    // factors modulo 3    vector<int> v(MAX, 0);Â
    // Stores the occurrences    // of the prime factors    map<vector<int>, int> mp;    mp[v]++;Â
    // Traverse the array, arr[]    for (int i = 0; i < n; i++) {Â
        // Store the prime factors        // and update the vector v        primeFactors(v, arr[i]);Â
        // Update the answer        ans += mp[v];Â
        // Increment current state        // of the prime factors by 1        mp[v]++;    }Â
    // Print the result    cout << ans;}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { 1, 8, 4, 2 };Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]);Â
    countSubarrays(arr, N);Â
    return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;Â
class GFG{Â
static int MAX = (int)(1e5);Â
// To store the arr as a Key in mapstatic 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;    }}Â
// Function to store the prime// factorization of a numberstatic void primeFactors(int v[], int n){    for(int i = 2; i * i <= n; i++)    {                 // If N is divisible by i        while (n % i == 0)        {                         // Increment v[i] by 1 and            // calculate it modulo by 3            v[i]++;            v[i] %= 3;Â
            // Divide the number by i            n /= i;        }    }Â
    // If the number is not equal to 1    if (n != 1)    {                 // Increment v[n] by 1        v[n]++;Â
        // Calculate it modulo 3        v[n] %= 3;    }}Â
// Function to count the number of// subarrays whose product is a perfect cubestatic void countSubarrays(int arr[], int n){         // Store the required result    int ans = 0;Â
    // Stores the prime    // factors modulo 3    int v[] = new int[MAX];Â
    // Stores the occurrences    // of the prime factors    HashMap<Key, Integer> mp = new HashMap<>();    mp.put(new Key(v), 1);Â
    // Traverse the array, arr[]    for(int i = 0; i < n; i++)     {                 // Store the prime factors        // and update the vector v        primeFactors(v, arr[i]);Â
        // Update the answer        ans += mp.getOrDefault(new Key(v), 0);Â
        // Increment current state        // of the prime factors by 1        Key vv = new Key(v);        mp.put(vv, mp.getOrDefault(vv, 0) + 1);    }Â
    // Print the result    System.out.println(ans);}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int arr[] = { 1, 8, 4, 2 };Â Â Â Â int N = arr.length;Â
    countSubarrays(arr, N);}}Â
// This code is contributed by Kingash |
Python3
from typing import Listfrom collections import defaultdictÂ
MAX = (int)(1e5)Â
# To store the arr as a Key in mapclass Key:Â Â Â Â def __init__(self, arr):Â Â Â Â Â Â Â Â self.arr = arrÂ
    def __hash__(self):        return 31 + hash(tuple(self.arr))Â
    def __eq__(self, other):        return self.arr == other.arrÂ
# Function to store the prime# factorization of a numberdef primeFactors(v: List[int], n: int):    for i in range(2, int(n ** 0.5) + 1):                 # If N is divisible by i        while n % i == 0:                         # Increment v[i] by 1 and            # calculate it modulo by 3            v[i] += 1            v[i] %= 3Â
            # Divide the number by i            n /= i    # If the number is not equal to 1    if n != 1:                 # Increment v[n] by 1        v[n] += 1Â
        # Calculate it modulo 3        v[n] %= 3Â
# Function to count the number of# subarrays whose product is a perfect cubedef countSubarrays(arr: List[int], n: int):         # Store the required result    ans = 0Â
    # Stores the prime    # factors modulo 3    v = [0] * MAXÂ
    # Stores the occurrences    # of the prime factors    mp = defaultdict(int)    mp[Key(v)] = 1Â
    # Traverse the array, arr[]    for i in range(n):                  # Store the prime factors        # and update the vector v        primeFactors(v, arr[i])Â
        # Update the answer        ans += mp[Key(v)]Â
        # Increment current state        # of the prime factors by 1        vv = Key(v)        mp[vv] += 1    # Print the result    print(ans)Â
# Driver Codearr = [1, 8, 4, 2]N = len(arr)Â
countSubarrays(arr, N)Â
# This code is contributed by aadityaburujwale. |
C#
using System;using System.Collections.Generic;using System.Linq;Â
class GFG{Â Â static int MAX = (int)(1e5);Â
  // To store the arr as a Key in map  class Key  {    int[] arr;Â
    public Key(int[] arr)    {      this.arr = arr;    }Â
    public override int GetHashCode()    {      return 31 + arr.GetHashCode();    }Â
    public override bool Equals(object obj)    {      if (this == obj)        return true;      if (obj == null ||          (GetType() != obj.GetType()))        return false;Â
      Key other = (Key)obj;Â
      if (!arr.SequenceEqual(other.arr))        return false;Â
      return true;    }  }Â
  // Function to store the prime  // factorization of a number  static void primeFactors(int[] v, int n)  {    for (int i = 2; i * i <= n; i++)    {      // If N is divisible by i      while (n % i == 0)      {        // Increment v[i] by 1 and        // calculate it modulo by 3        v[i]++;        v[i] %= 3;Â
        // Divide the number by i        n /= i;      }    }Â
    // If the number is not equal to 1    if (n != 1)    {      // Increment v[n] by 1      v[n]++;Â
      // Calculate it modulo 3      v[n] %= 3;    }  }Â
  // Function to count the number of  // subarrays whose product is a perfect cube  static void countSubarrays(int[] arr, int n)  {    // Store the required result    int ans = 0;Â
    // Stores the prime    // factors modulo 3    int[] v = new int[MAX];Â
    // Stores the occurrences    // of the prime factors    Dictionary<Key, int> mp = new Dictionary<Key, int>();    mp[new Key(v)] = 1;Â
    // Traverse the array, arr[]    for (int i = 0; i < n-1; i++)    {      // Store the prime factors      // and update the vector v      primeFactors(v, arr[i]);Â
      // Update the answer      ans += mp.GetValueOrDefault(new Key(v), 0);Â
      // Increment current state      // of the prime factors by 1      Key vv = new Key(v);      mp[vv] = mp.GetValueOrDefault(vv, 0) + 1;    }Â
    // Print the result    Console.WriteLine(ans);  }Â
  // Driver Code  public static void Main(string[] args)  {    int[] arr = { 1, 8, 4, 2 };    int N = arr.Length;Â
    countSubarrays(arr, N);  }}Â
Â
// This code is contributed by aadityaburujwale. |
Javascript
// JavaScript program for the above approachfunction primeFactors(v, n) {Â Â Â Â for (let i = 2; i * i <= n; i++) {Â
        // If N is divisible by i        while (n % i == 0) {Â
            // Increment v[i] by 1 and            // calculate it modulo by 3            v[i]++;            v[i] %= 3;Â
            // Divide the number by i            n /= i;        }    }Â
    // If the number is not equal to 1    if (n != 1) {Â
        // Increment v[n] by 1        v[n]++;Â
        // Calculate it modulo 3        v[n] %= 3;    }}Â
// Function to count the number of// subarrays whose product is a perfect cubefunction countSubarrays(arr, n) {    // Store the required result    let ans = 0;Â
    // Stores the prime    // factors modulo 3    let v = Array(1e5).fill(0);Â
    // Stores the occurrences    // of the prime factors    let mp = new Map();    mp.set(v, 1);Â
    // Traverse the array, arr[]    for (let i = 0; i < n; i++) {Â
        // Store the prime factors        // and update the vector v        primeFactors(v, arr[i]);Â
        // Update the answer        ans += mp.get(v)-1;Â
        // Increment current state        // of the prime factors by 1        mp.set(v, mp.get(v) + 1);    }Â
    // Print the result    console.log(ans);}Â
// Driver Codelet arr = [1, 8, 4, 2];let N = arr.length;Â
countSubarrays(arr, N);// contributed by akashish__ |
6
Â
Time Complexity: O(N3/2)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/count-of-subarrays-having-product-as-a-perfect-cube/ […]