Dada una array arr[] que consta de N enteros positivos, la tarea es contar el número de subarreglos con el producto de sus elementos igual a un cubo perfecto .
Ejemplos:
Entrada: arr[] = {1, 8, 4, 2}
Salida: 6
Explicación:
Los subarreglos con producto de elementos igual a un cubo perfecto son:
- {1}. Por lo tanto, producto de subarreglo = 1 (= (1) 3 ).
- {1, 8}. Por lo tanto, producto de subarreglo = 8 ( = 2 3 ).
- {8}. Por lo tanto, producto de subarreglo = 8 = (2 3 ).
- {4, 2}. Por lo tanto, producto de subarreglo = 8 (= 2 3 ).
- {8, 4, 2}. Por lo tanto, producto de subarreglo = 64 (= 4 3 ).
- {1, 8, 4, 2}. Por lo tanto, producto de subarreglo = 64 (= 4 3 ).
Por lo tanto, la cuenta total es 6.
Entrada: arr[] = {10, 10,10}
Salida: 1
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles a partir del arreglo dado y contar esos subarreglos cuyo producto de los elementos del subarreglo es un cubo perfecto . Después de verificar todos los subarreglos , imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number
// is perfect cube or not
bool 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 cube
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
cout << ans;
}
// Driver Code
int 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 not def 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 cube def 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 Code if __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 approach
using System;
public class GFG
{
// Driver Code
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
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>
Producción:
6
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando la cantidad de factores primos módulo 3 en un HashMap mientras se recorre la array y se cuentan los cubos perfectos en consecuencia. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans, para almacenar el resultado requerido, y una array V con 0 para almacenar la frecuencia de los factores primos mod 3 para cada elemento en la array dada arr[] .
- Inicialice un Hashmap , digamos M, para almacenar la frecuencia del estado actual de los factores primos e incremente V en 1 en el HashMap.
- Atraviese la array arr[] usando la variable realizo los siguientes pasos:
- Almacene la frecuencia de los factores primos mod 3 de arr[i] en V .
- Incremente el valor de ans por la frecuencia de V en M y luego incremente el valor de V en M .
- Después de completar los pasos anteriores. imprime el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
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 number
void 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 cube
void 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 Code
int 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 approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
static int MAX = (int)(1e5);
// To store the arr as a Key in map
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;
}
}
// 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
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 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 Kingash
Producción:
6
Complejidad temporal: O(N 3/2 )
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por abhinavjain194 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA