Given a number N, the task is to find the minimum value K such that the sum of cubes of the first K natural number is greater than or equal to N.
Examples:
Input: N = 100
Output: 4
Explanation:
The sum of cubes of first 4 natural number is 100 which is equal to N = 100Input: N = 15
Output: 3
Explanation:
The sum of cubes of first 2 natural number is 9 which is lesser than K = 15 and sum of first
3 natural number is 36 which is just greater than K. So the answer is 3.
Naive Approach: The naive approach for this problem is to run a loop from and find the sum of cubes. Whenever the sum exceeds the value of N, break from the loop.
Below is the implementation of the above approach:
C++
// C++ program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to N#include <bits/stdc++.h>using namespace std;// Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nint naive_find_x(int N){ // Variable to store the // sum of cubes int c = 0, i; // Loop to find the number // K for(i = 1; i < N; i++) { c += i * i * i; // If C is just greater than // N, then break the loop if (c >= N) break; } return i;}// Driver codeint main(){ int N = 100; cout << naive_find_x(N); return 0;}// This code is contributed by sapnasingh4991 |
Java
// Java program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to Nclass GFG { // Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nstatic int naive_find_x(int N){ // Variable to store the // sum of cubes int c = 0, i; // Loop to find the number // K for(i = 1; i < N; i++) { c += i * i * i; // If C is just greater than // N, then break the loop if (c >= N) break; } return i;}// Driver codepublic static void main(String[] args){ int N = 100; System.out.println(naive_find_x(N));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to N# Function to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to Ndef naive_find_x(N): # Variable to store the # sum of cubes c = 0 # Loop to find the number # K for i in range(1, N): c += i*i*i # If C is just greater than # N, then break the loop if c>= N: break return i# Driver codeif __name__ == "__main__": N = 100 print(naive_find_x(N)) |
C#
// C# program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to Nusing System;class GFG { // Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nstatic int naive_find_x(int N){ // Variable to store the // sum of cubes int c = 0, i; // Loop to find the number // K for(i = 1; i < N; i++) { c += i * i * i; // If C is just greater than // N, then break the loop if (c >= N) break; } return i;}// Driver codepublic static void Main(String[] args){ int N = 100; Console.WriteLine(naive_find_x(N));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to N// Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nfunction naive_find_x(N){ // Variable to store the // sum of cubes var c = 0, i; // Loop to find the number // K for(i = 1; i < N; i++) { c += i * i * i; // If C is just greater than // N, then break the loop if (c >= N) break; } return i;}// Driver codevar N = 100;document.write(naive_find_x(N));// This code is contributed by Amit Katiyar </script> |
Output:
4
Time Complexity: O(K), where K is the number which needs to be found.
Auxiliary Space: O(1) because it is using constant space for variables
Efficient Approach: One observation which needs to be made is that the sum of cubes first N natural numbers is given by the formula:
sum = ((N * (N + 1))/2)2
And, this is a monotonically increasing function. Therefore, the idea is to apply binary search to find the value of K. If the sum is greater than N for some number ‘i’, then we know that the answer is less than or equal to ‘i’. So, iterate to the left half. Else, iterate through the right half.
Below is the implementation of the above approach:
C++
// C++ program to determine the // minimum value of K such that // the sum of cubes of first K // natural number is greater than // or equal to N#include <bits/stdc++.h>using namespace std; // Function to determine the// minimum value of K such that // the sum of cubes of first K// natural number is greater than// or equal to Nint binary_searched_find_x(int k) { // Left bound int l = 0; // Right bound int r = k; // Variable to store the // answer int ans = 0; // Applying binary search while (l <= r) { // Calculating mid value // of the range int mid = l + (r - l) / 2; if (pow(((mid * (mid + 1)) / 2), 2) >= k) { // If the sum of cubes of // first mid natural numbers // is greater than equal to N // iterate the left half ans = mid; r = mid - 1; } else { // Sum of cubes of first // mid natural numbers is // less than N, then move // to the right segment l = mid + 1; } } return ans;}// Driver codeint main() { int N = 100; cout << binary_searched_find_x(N); return 0;}// This code is contributed by shubhamsingh10 |
Java
// Java program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to Nclass GFG{ // Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nstatic int binary_searched_find_x(int k) { // Left bound int l = 0; // Right bound int r = k; // Variable to store the // answer int ans = 0; // Applying binary search while (l <= r) { // Calculating mid value // of the range int mid = l + (r - l) / 2; if (Math.pow(((mid * (mid + 1)) / 2), 2) >= k) { // If the sum of cubes of // first mid natural numbers // is greater than equal to N // iterate the left half ans = mid; r = mid - 1; } else { // Sum of cubes of first // mid natural numbers is // less than N, then move // to the right segment l = mid + 1; } } return ans;}// Driver codepublic static void main(String[] args) { int N = 100; System.out.println(binary_searched_find_x(N));}}// This code is contributed by 29AjayKumar |
Python3
# Python program to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to N# Function to determine the # minimum value of K such that the # sum of cubes of first K # natural number is greater than # or equal to Ndef binary_searched_find_x(k): # Left bound l = 0 # Right bound r = k # Variable to store the # answer ans = 0 # Applying binary search while l<= r: # Calculating mid value # of the range mid = l+(r-l)//2 if ((mid*(mid + 1))//2)**2>= k: # If the sum of cubes of # first mid natural numbers # is greater than equal to N # iterate the left half ans = mid r = mid-1 else: # Sum of cubes of first # mid natural numbers is # less than N, then move # to the right segment l = mid + 1 return ans # Driver codeif __name__ == "__main__": N = 100 print(binary_searched_find_x(N)) |
C#
// C# program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to Nusing System;class GFG{ // Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nstatic int binary_searched_find_x(int k) { // Left bound int l = 0; // Right bound int r = k; // Variable to store the // answer int ans = 0; // Applying binary search while (l <= r) { // Calculating mid value // of the range int mid = l + (r - l) / 2; if (Math.Pow(((mid * (mid + 1)) / 2), 2) >= k) { // If the sum of cubes of // first mid natural numbers // is greater than equal to N // iterate the left half ans = mid; r = mid - 1; } else { // Sum of cubes of first // mid natural numbers is // less than N, then move // to the right segment l = mid + 1; } } return ans;}// Driver codepublic static void Main() { int N = 100; Console.Write(binary_searched_find_x(N));}}// This code is contributed by Nidhi_biet |
Javascript
<script>// javascript program to determine the // minimum value of K such that the // sum of cubes of first K // natural number is greater than // or equal to N // Function to determine the// minimum value of K such that the// sum of cubes of first K// natural number is greater than// or equal to Nfunction binary_searched_find_x(k) { // Left bound var l = 0; // Right bound var r = k; // Variable to store the // answer var ans = 0; // Applying binary search while (l <= r) { // Calculating mid value // of the range var mid = parseInt(l + (r - l) / 2); if (Math.pow(((mid * (mid + 1)) / 2), 2) >= k) { // If the sum of cubes of // first mid natural numbers // is greater than equal to N // iterate the left half ans = mid; r = mid - 1; } else { // Sum of cubes of first // mid natural numbers is // less than N, then move // to the right segment l = mid + 1; } } return ans;}// Driver codevar N = 100;document.write(binary_searched_find_x(N));// This code contributed by shikhasingrajput </script> |
Output:
4
Time Complexity: O(log(K)).
Auxiliary Space: O(1) because it is using constant variables
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.
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
