Dada una array arr[] , la tarea es contar los subarreglos que tienen suma como un cubo perfecto.
Ejemplos:
Entrada: arr[] = {6, 10, 9, 2, 1, 113}
Salida: 3
Explicación:
Los subarreglos con suma de elementos igual a un cubo perfecto son:
- {1}. Por lo tanto, suma de subarreglo = 1 (= 1^3).
- {6, 10, 9, 2}. Por lo tanto, suma de subarreglo = 27 ( = 3^3).
- {9, 2, 1, 113}. Por lo tanto, suma de subarreglo = 125 ( = 5^3).
Entrada: arr[] = {1}
Salida: 1
Explicación:
Solo existe un subarreglo cuya suma es un cubo perfecto
Enfoque: La idea es encontrar la suma del prefijo de la array de modo que la suma de cualquier subarreglo pueda calcularse en O(1). Luego itere sobre cada subarreglo posible y verifique que la suma del subarreglo sea un cubo perfecto, si es así, incremente el conteo en 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count
// subarrays having sum
// as a perfect cube
#include <bits/stdc++.h>
using namespace std;
#define int long long
// Function to check for
// perfect cube or not
bool isCubicSquare(int x)
{
int curoot = round(pow(x, 1.0 / 3.0));
if (curoot * curoot * curoot == x)
return true;
return false;
}
// Function to count the subarray
// whose sum is a perfect cube
int count(int arr[], int n)
{
int pre[n + 1];
pre[0] = 0;
// Loop to find the prefix sum
// of the array
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + arr[i - 1];
}
int ans = 0;
// Loop to take every
// possible subarrays
for (int i = 0; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
// check for every
// possible subarrays
if (isCubicSquare((double)
(pre[j] - pre[i]))) {
ans++;
}
}
}
return ans;
}
// Driver Code
int32_t main()
{
int arr[6] = { 6, 10, 9, 2, 1, 113 };
cout << count(arr, 6);
return 0;
}
Java
// Java implementation to count subarrays
// having sum as a perfect cube
import java.lang.Math;
class GFG{
// Function to check for
// perfect cube or not
public static boolean isCubicSquare(int x)
{
double curoot = Math.round(
Math.pow(x, 1.0 / 3.0));
if (curoot * curoot * curoot == x)
return true;
return false;
}
// Function to count the subarray
// whose sum is a perfect cube
public static int count(int arr[], int n)
{
int[] pre = new int[n + 1];
pre[0] = 0;
// Loop to find the prefix sum
// of the array
for(int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1] + arr[i - 1];
}
int ans = 0;
// Loop to take every
// possible subarrays
for(int i = 0; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
// Check for every
// possible subarrays
if (isCubicSquare((pre[j] - pre[i])))
{
ans++;
}
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 10, 9, 2, 1, 113 };
System.out.print(count(arr, 6));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation to count # subarrays having sum # as a perfect cube # Function to check for # perfect cube or not def isCubicSquare(x): curoot = round(pow(x, 1.0 / 3.0)) if (curoot * curoot * curoot == x): return True return False # Function to count the subarray # whose sum is a perfect cube def count(arr, n): pre = [0] * (n + 1) pre[0] = 0 # Loop to find the prefix # sum of the array for i in range (1, n + 1): pre[i] = pre[i - 1] + arr[i - 1] ans = 0 # Loop to take every # possible subarrays for i in range (n + 1): for j in range (i + 1, n + 1): # Check for every # possible subarrays if (isCubicSquare((pre[j] - pre[i]))): ans += 1 return ans # Driver Code if __name__ == "__main__": arr = [6, 10, 9, 2, 1, 113] print (count(arr, 6)) # This code is contributed by Chitranayal
C#
// C# implementation to count subarrays
// having sum as a perfect cube
using System;
class GFG{
// Function to check for
// perfect cube or not
public static bool isCubicSquare(int x)
{
double curoot = Math.Round(
Math.Pow(x, 1.0 / 3.0));
if (curoot * curoot * curoot == x)
return true;
return false;
}
// Function to count the subarray
// whose sum is a perfect cube
public static int count(int []arr, int n)
{
int[] pre = new int[n + 1];
pre[0] = 0;
// Loop to find the prefix sum
// of the array
for(int i = 1; i <= n; i++)
{
pre[i] = pre[i - 1] + arr[i - 1];
}
int ans = 0;
// Loop to take every
// possible subarrays
for(int i = 0; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
// Check for every
// possible subarrays
if (isCubicSquare((pre[j] - pre[i])))
{
ans++;
}
}
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 6, 10, 9, 2, 1, 113 };
Console.Write(count(arr, 6));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation to count
// subarrays having sum
// as a perfect cube
// Function to check for
// perfect cube or not
function isCubicSquare( x)
{
var curoot = Math.round(Math.pow(x, 1.0 / 3.0));
if (curoot * curoot * curoot == x)
return true;
return false;
}
// Function to count the subarray
// whose sum is a perfect cube
function count(arr, n)
{
var pre = Array(n+1);
pre[0] = 0;
// Loop to find the prefix sum
// of the array
for (var i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + arr[i - 1];
}
var ans = 0;
// Loop to take every
// possible subarrays
for (var i = 0; i <= n; i++) {
for (var j = i + 1; j <= n; j++) {
// check for every
// possible subarrays
if (isCubicSquare(
(pre[j] - pre[i]))) {
ans++;
}
}
}
return ans;
}
// Driver Code
var arr = [6, 10, 9, 2, 1, 113 ];
document.write( count(arr, 6));
// This code is contributed by itsok.
</script>
Producción:
3
Análisis de rendimiento:
- Complejidad temporal: O(N 2 )
- Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA