Dada una array de n enteros, cuente todos los tripletes diferentes cuya suma sea igual al cubo perfecto, es decir, para cualquier i, j, k(i < j < k) que satisfaga la condición de que a[i] + a[j] + a [j] = X 3 donde X es cualquier número entero. 3 ≤ norte ≤ 1000, 1 ≤ un[i, j, k] ≤ 5000
Ejemplo:
Input: N = 5 2 5 1 20 6 Output: 3 Explanation: There are only 3 triplets whose total sum is a perfect cube. Indices Values SUM 0 1 2 2 5 1 8 0 1 3 2 5 20 27 2 3 4 1 20 6 27 Since 8 and 27 are perfect cube of 2 and 3.
El enfoque ingenuo es iterar sobre todos los números posibles usando 3 bucles anidados y verificar si su suma es un cubo perfecto o no. El enfoque sería muy lento ya que la complejidad del tiempo puede llegar a O(n 3 ).
Un enfoque eficiente es usar programación dinámica y matemáticas básicas. De acuerdo con la condición dada, la suma de cualquiera de los tres enteros positivos no es mayor que 15000. Por lo tanto, solo puede haber 24 (15000 1/3 ) cubos posibles en el rango de 1 a 15000.
Ahora, en lugar de iterar todos los tripletes, podemos hacer mucho mejor con la ayuda de la información anterior. Se corrigieron los dos primeros índices i y j de modo que en lugar de iterar sobre todos los k(j < k ≤ n), podemos iterar sobre los 24 cubos posibles, y para cada uno, (digamos P) verificar cuántas ocurrencias de P – (a[i] + a[j]) están en a[j+1, j+2, … n].
Pero si calculamos el número de ocurrencias de un número, digamos K en a[j+1, j+2, … n], entonces esto nuevamente se contaría como un enfoque lento y definitivamente daría TLE. Así que tenemos que pensar en un enfoque diferente.
Ahora aquí viene una Programación Dinámica. Dado que todos los números son menores que 5000 y n es como máximo 1000. Por lo tanto, podemos calcular una array DP como,
dp[i][K]:= Número de ocurrencias de K en A[i, i+1, i+2… norte]
C++
// C++ program to calculate all triplets whose
// sum is perfect cube.
#include <bits/stdc++.h>
using namespace std;
int dp[1001][15001];
// Function to calculate all occurrence of
// a number in a given range
void computeDpArray(int arr[], int n)
{
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= 15000; ++j) {
// if i == 0
// assign 1 to present state
if (i == 0)
dp[i][j] = (j == arr[i]);
// else add +1 to current state with
// previous state
else
dp[i][j] = dp[i - 1][j] + (arr[i] == j);
}
}
}
// Function to calculate triplets whose sum
// is equal to the perfect cube
int countTripletSum(int arr[], int n)
{
computeDpArray(arr, n);
int ans = 0; // Initialize answer
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = 1; k <= 24; ++k) {
int cube = k * k * k;
int rem = cube - (arr[i] + arr[j]);
// count all occurrence of third triplet
// in range from j+1 to n
if (rem > 0)
ans += dp[n - 1][rem] - dp[j][rem];
}
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 5, 1, 20, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countTripletSum(arr, n);
return 0;
}
Java
// JAVA Code for Count all triplets whose
// sum is equal to a perfect cube
import java.util.*;
class GFG {
public static int dp[][];
// Function to calculate all occurrence of
// a number in a given range
public static void computeDpArray(int arr[], int n)
{
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= 15000; ++j) {
// if i == 0
// assign 1 to present state
if (i == 0 && j == arr[i])
dp[i][j] = 1;
else if(i==0)
dp[i][j] = 0;
// else add +1 to current state
// with previous state
else if(arr[i] == j)
dp[i][j] = dp[i - 1][j] + 1;
else
dp[i][j] = dp[i - 1][j];
}
}
}
// Function to calculate triplets whose sum
// is equal to the perfect cube
public static int countTripletSum(int arr[], int n)
{
computeDpArray(arr, n);
int ans = 0; // Initialize answer
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = 1; k <= 24; ++k) {
int cube = k * k * k;
int rem = cube - (arr[i] + arr[j]);
// count all occurrence of
// third triplet in range
// from j+1 to n
if (rem > 0)
ans += dp[n - 1][rem] - dp[j][rem];
}
}
}
return ans;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 2, 5, 1, 20, 6 };
int n = arr.length;
dp = new int[1001][15001];
System.out.println(countTripletSum(arr, n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python 3 program to calculate all # triplets whose sum is perfect cube. dp = [[0 for i in range(15001)] for j in range(1001)] # Function to calculate all occurrence # of a number in a given range def computeDpArray(arr, n): for i in range(n): for j in range(1, 15001, 1): # if i == 0 # assign 1 to present state if (i == 0): dp[i][j] = (j == arr[i]) # else add +1 to current state with # previous state else: dp[i][j] = dp[i - 1][j] + (arr[i] == j) # Function to calculate triplets whose # sum is equal to the perfect cube def countTripletSum(arr, n): computeDpArray(arr, n) ans = 0 # Initialize answer for i in range(0, n - 2, 1): for j in range(i + 1, n - 1, 1): for k in range(1, 25, 1): cube = k * k * k rem = cube - (arr[i] + arr[j]) # count all occurrence of third # triplet in range from j+1 to n if (rem > 0): ans += dp[n - 1][rem] - dp[j][rem] return ans # Driver code if __name__ == '__main__': arr = [2, 5, 1, 20, 6] n = len(arr) print(countTripletSum(arr, n)) # This code is contributed by # Sahil_Shelangia
C#
// C# Code for Count all triplets whose
// sum is equal to a perfect cube
using System;
class GFG
{
public static int [,]dp;
// Function to calculate all occurrence
// of a number in a given range
public static void computeDpArray(int []arr,
int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 1; j <= 15000; ++j)
{
// if i == 0
// assign 1 to present state
if (i == 0 && j == arr[i])
dp[i, j] = 1;
else if(i == 0)
dp[i, j] = 0;
// else add +1 to current state
// with previous state
else if(arr[i] == j)
dp[i, j] = dp[i - 1, j] + 1;
else
dp[i, j] = dp[i - 1, j];
}
}
}
// Function to calculate triplets whose
// sum is equal to the perfect cube
public static int countTripletSum(int []arr,
int n)
{
computeDpArray(arr, n);
int ans = 0; // Initialize answer
for (int i = 0; i < n - 2; ++i)
{
for (int j = i + 1; j < n - 1; ++j)
{
for (int k = 1; k <= 24; ++k)
{
int cube = k * k * k;
int rem = cube - (arr[i] + arr[j]);
// count all occurrence of
// third triplet in range
// from j+1 to n
if (rem > 0)
ans += dp[n - 1, rem] -
dp[j, rem];
}
}
}
return ans;
}
// Driver Code
public static void Main()
{
int []arr = { 2, 5, 1, 20, 6 };
int n = arr.Length;
dp = new int[1001, 15001];
Console.Write(countTripletSum(arr, n));
}
}
// This code is contributed
// by 29AjayKumar
PHP
<?php
// PHP program to calculate all triplets
// whose sum is perfect cube.
$dp = array_fill(0, 1001,
array_fill(0, 15001, NULL));
// Function to calculate all occurrence
// of a number in a given range
function computeDpArray(&$arr, $n)
{
global $dp;
for ($i = 0; $i < $n; ++$i)
{
for ($j = 1; $j <= 15000; ++$j)
{
// if i == 0
// assign 1 to present state
if ($i == 0)
$dp[$i][$j] = ($j == $arr[$i]);
// else add +1 to current state with
// previous state
else
$dp[$i][$j] = $dp[$i - 1][$j] +
($arr[$i] == $j);
}
}
}
// Function to calculate triplets whose
// sum is equal to the perfect cube
function countTripletSum(&$arr, $n)
{
global $dp;
computeDpArray($arr, $n);
$ans = 0; // Initialize answer
for ($i = 0; $i < $n - 2; ++$i)
{
for ($j = $i + 1; $j < $n - 1; ++$j)
{
for ($k = 1; $k <= 24; ++$k)
{
$cube = $k * $k * $k;
$rem = $cube - ($arr[$i] + $arr[$j]);
// count all occurrence of third
// triplet in range from j+1 to n
if ($rem > 0)
$ans += $dp[$n - 1][$rem] -
$dp[$j][$rem];
}
}
}
return $ans;
}
// Driver code
$arr = array(2, 5, 1, 20, 6);
$n = sizeof($arr);
echo countTripletSum($arr, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// JavaScript Code for Count all triplets whose
// sum is equal to a perfect cube
let dp = new Array(1001);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
// Function to calculate all occurrence of
// a number in a given range
function computeDpArray(arr, n)
{
for (let i = 0; i < n; ++i) {
for (let j = 1; j <= 15000; ++j) {
// if i == 0
// assign 1 to present state
if (i == 0 && j == arr[i])
dp[i][j] = 1;
else if(i==0)
dp[i][j] = 0;
// else add +1 to current state
// with previous state
else if(arr[i] == j)
dp[i][j] = dp[i - 1][j] + 1;
else
dp[i][j] = dp[i - 1][j];
}
}
}
// Function to calculate triplets whose sum
// is equal to the perfect cube
function countTripletSum(arr, n)
{
computeDpArray(arr, n);
let ans = 0; // Initialize answer
for (let i = 0; i < n - 2; ++i)
{
for (let j = i + 1; j < n - 1; ++j)
{
for (let k = 1; k <= 24; ++k)
{
let cube = k * k * k;
let rem = cube - (arr[i] + arr[j]);
// count all occurrence of
// third triplet in range
// from j+1 to n
if (rem > 0)
ans += dp[n - 1][rem] - dp[j][rem];
}
}
}
return ans;
}
// Driver Code
let arr = [ 2, 5, 1, 20, 6 ];
let n = arr.length;
dp = new Array(1001);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
}
document.write(countTripletSum(arr, n));
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
3
Complejidad temporal: O(N 2 *24)
Espacio auxiliar: O(10 7 )
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA