Given an array arr[], the task is to count the subarrays having sum as a perfect cube.
Examples:
Input: arr[] = {6, 10, 9, 2, 1, 113}
Output: 3
Explanation:
The subarrays with sum of elements equal to a perfect cube are:
- {1}. Therefore, sum of subarray = 1 (= 1^3).
- {6, 10, 9, 2}. Therefore, sum of subarray = 27 ( = 3^3).
- {9, 2, 1, 113}. Therefore, sum of subarray = 125 ( = 5^3).
Input: arr[] = {1}
Output: 1
Explanation:
There is only one such subarray whose sum is a perfect cube
Approach: The idea is to find the prefix sum of the array such that the sum of any subarray can be computed in O(1). Then iterate over every possible subarray and check that the sum of the subarray is a perfect cube if yes then increment the count by 1.
Below is the implementation of the above approach:
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 notbool 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 cubeint 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 Codeint32_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 cubeimport 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 codepublic 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 notdef 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 cubedef 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 Codeif __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 cubeusing 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 codepublic 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 notfunction 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 cubefunction 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 Codevar arr = [6, 10, 9, 2, 1, 113 ];document.write( count(arr, 6));// This code is contributed by itsok.</script> |
Output:
3
Performance Analysis:
- Time Complexity: O(N2 log N)
- Auxiliary Space: O(N)
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!
