Sum of all Perfect Cubes lying in the range [L, R] for Q queries
Given Q queries in the form of 2D array arr[][] whose every row consists of two numbers L and R which signifies the range [L, R], the task is to find the sum of all perfect cubes lying in this range.
Examples:
Input: Q = 2, arr[][] = {{4, 9}, {4, 44}}
Output: 8 35
From 4 to 9: only 8 is the perfect cube. Therefore, 8 is the ans
From 4 to 44: 8, and 27 are the perfect cubes. Therefore, 8 + 27 = 35
Input: Q = 4, arr[][] = {{ 1, 10 }, { 1, 100 }, { 2, 25 }, { 4, 50 }}
Output: 9 100 8 35
Approach: The idea is to use a prefix sum array.
- The sum all cubes are precomputed and stored in an array pref[] so that every query can be answered in O(1) time.
- Every ith index in the pref[] array represents the sum of perfect cubes from 1 to that number.
- Therefore, the sum of perfect cubes from the given range ‘L’ to ‘R’ can be found as from the prefix sum array pref[].
Below is the implementation of the above approach:
C++
// C++ program to find the sum of all // perfect cubes in the given range #include <bits/stdc++.h> #define ll int using namespace std; // Array to precompute the sum of cubes // from 1 to 100010 so that for every // query, the answer can be returned in O(1). long long pref[100010]; // Function to check if a number is // a perfect Cube or not int isPerfectCube( long long int x) { // Find floating point value of // cube root of x. long double cr = round(cbrt(x)); // If cube root of x is cr // return the x, else 0 return (cr * cr * cr == x) ? x : 0; } // Function to precompute the perfect // Cubes upto 100000. void compute() { for ( int i = 1; i <= 100000; ++i) { pref[i] = pref[i - 1] + isPerfectCube(i); } } // Function to print the sum for each query void printSum( int L, int R) { int sum = pref[R] - pref[L - 1]; cout << sum << " " ; } // Driver code int main() { // To calculate the precompute function compute(); int Q = 4; int arr[][2] = { { 1, 10 }, { 1, 100 }, { 2, 25 }, { 4, 50 } }; // Calling the printSum function // for every query for ( int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } return 0; } |
Java
// Java program to find the sum of all // perfect cubes in the given range import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class GFG { // Array to precompute the sum of cubes // from 1 to 100010 so that for every // query, the answer can be returned in O(1). public static int []pref= new int [ 100010 ]; // Function to check if a number is // a perfect Cube or not static int isPerfectCube( int x) { // Find floating point value of // cube root of x. double cr = Math.round(Math.cbrt(x)); // If cube root of x is cr // return the x, else 0 if (cr*cr*cr==( double )x) return x; return 0 ; } // Function to precompute the perfect // Cubes upto 100000. static void compute() { for ( int i = 1 ; i <= 100000 ; ++i) { pref[i] = pref[i - 1 ]+ isPerfectCube(i); } } // Function to print the sum for each query static void printSum( int L, int R) { long sum = pref[R] - pref[L - 1 ]; System.out.print(sum+ " " ); } // Driver code public static void main (String[] args) { // To calculate the precompute function compute(); int Q = 4 ; int [][] arr = { { 1 , 10 }, { 1 , 100 }, { 2 , 25 }, { 4 , 50 } }; // Calling the printSum function // for every query for ( int i = 0 ; i < Q; i++) { printSum(arr[i][ 0 ], arr[i][ 1 ]); } } } // This code is contributed by chitranayal |
Python3
# Python3 program to find the sum of all # perfect cubes in the given range # Array to precompute the sum of cubes # from 1 to 100010 so that for every # query, the answer can be returned in O(1). pref = [ 0 ] * 100010 ; # Function to check if a number is # a perfect Cube or not def isPerfectCube(x) : # Find floating point value of # cube root of x. cr = round (x * * ( 1 / 3 )); # If cube root of x is cr # return the x, else 0 rslt = x if (cr * cr * cr = = x) else 0 ; return rslt; # Function to precompute the perfect # Cubes upto 100000. def compute() : for i in range ( 1 , 100001 ) : pref[i] = pref[i - 1 ] + isPerfectCube(i); # Function to print the sum for each query def printSum(L, R) : sum = pref[R] - pref[L - 1 ]; print ( sum ,end = " " ); # Driver code if __name__ = = "__main__" : # To calculate the precompute function compute(); Q = 4 ; arr = [ [ 1 , 10 ], [ 1 , 100 ], [ 2 , 25 ], [ 4 , 50 ] ]; # Calling the printSum function # for every query for i in range (Q) : printSum(arr[i][ 0 ], arr[i][ 1 ]); # This code is contributed by AnkitRai01 |
C#
// C# program to find the sum of all // perfect cubes in the given range using System; class GFG { // Array to precompute the sum of cubes // from 1 to 100010 so that for every // query, the answer can be returned in O(1). public static long []pref= new long [100010]; // Function to check if a number is // a perfect Cube or not static long isPerfectCube( long x) { // Find floating point value of // cube root of x. double cr = Math.Round(MathF.Cbrt(x)); // If cube root of x is cr // return the x, else 0 if (cr*cr*cr==( double )x) return x; return 0; } // Function to precompute the perfect // Cubes upto 100000. static void compute() { for ( long i = 1; i <= 100000; ++i) { pref[i] = pref[i - 1] + isPerfectCube(i); } } // Function to print the sum for each query static void printSum( int L, int R) { long sum = pref[R] - pref[L - 1]; Console.Write(sum+ " " ); } // Driver code public static void Main() { // To calculate the precompute function compute(); int Q = 4; int [,] arr = new int [,]{ { 1, 10 }, { 1, 100 }, { 2, 25 }, { 4, 50 } }; // Calling the printSum function // for every query for ( int i = 0; i < Q; i++) { printSum(arr[i,0], arr[i,1]); } } } // This code is contributed by mohit kumar 29 |
Javascript
<script> // Javascript program to find the sum of all // perfect cubes in the given range // Array to precompute the sum of cubes // from 1 to 100010 so that for every // query, the answer can be returned in O(1). var pref=Array(100010).fill(0); // Function to check if a number is // a perfect Cube or not function isPerfectCube(x) { // Find floating point value of // cube root of x. var cr = Math.round(Math.cbrt(x)); // If cube root of x is cr // return the x, else 0 return (cr * cr * cr == x) ? x : 0; } // Function to precompute the perfect // Cubes upto 100000. function compute() { for ( var i = 1; i <= 100000; ++i) { pref[i] = pref[i - 1] + isPerfectCube(i); } } // Function to print the sum for each query function printSum(L, R) { var sum = pref[R] - pref[L - 1]; document.write(sum + " " ); } // Driver code // To calculate the precompute function compute(); var Q = 4; var arr = [ [ 1, 10 ], [ 1, 100 ], [ 2, 25 ], [ 4, 50 ] ]; // Calling the printSum function // for every query for ( var i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } </script> |
Output:
9 100 8 35
Time Complexity: O(100000)
Auxiliary Space: O(100010)