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> |
Output:
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 defaultdictMAX = (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__ |
Output:
6
Time Complexity: O(N3/2)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
