Given an array of n integers, count all different triplets whose sum is equal to the perfect cube i.e, for any i, j, k(i < j < k) satisfying the condition that a[i] + a[j] + a[j] = X3 where X is any integer. 3 ? n ? 1000, 1 ? a[i, j, k] ? 5000
Example:
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.
Naive approach is to iterate over all the possible numbers by using 3 nested loops and check whether their sum is a perfect cube or not. The approach would be very slow as time complexity can go up to O(n3).
An Efficient approach is to use dynamic programming and basic mathematics. According to the given condition sum of any of three positive integers is not greater than 15000. Therefore there can be only 24(150001/3) cubes are possible in the range of 1 to 15000.
Now instead of iterating all triplets we can do much better by the help of above information. Fixed first two indices i and j such that instead of iterating over all k(j < k ? n), we can iterate over all the 24 possible cubes, and for each one, (let’s say P) check how many occurrence of P – (a[i] + a[j]) are in a[j+1, j+2, … n].
But if we compute the number of occurrences of a number say K in a[j+1, j+2, … n] then this would again be counted as slow approach and would definitely give TLE. So we have to think of a different approach.
Now here comes to a Dynamic Programming. Since all numbers are smaller than 5000 and n is at most 1000. Hence we can compute a DP array as,
dp[i][K]:= Number of occurrence of K in A[i, i+1, i+2 … n]
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 rangevoid 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 cubeint 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 codeint 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 cubeimport 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 rangedef 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 cubedef 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 codeif __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 cubeusing System;class GFG {public static int [,]dp;// Function to calculate all occurrence // of a number in a given rangepublic 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 cubepublic 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 Codepublic 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 rangefunction 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 cubefunction 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> |
Output:
3
Time complexity: O(N2*24)
Auxiliary space: O(107)
This article is contributed by Shubham Bansal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
