PROBLEM LINK:
Author: A Rupeswar Subudhi
Tester: Pritish Priyatosh Nayak
Editorialist: Debanshu Sekhar Jena
DIFFICULTY:
Easy
PREREQUISITES:
Implementation, Brute Force, Data Structure (Set)
PROBLEM:
Find 3 numbers such that all of them are perfect cube and their sum is N.
In short we have to find 3 numbers, let’s say a, b, c such that a^3+b^3+c^3=N. Then Print a^3, b^3, c^3 in non-decreasing order.
EXPLANATION:
Simply bruteforce this problem, but a bit smartly. Instead of iterating upto N, iterate upto N^{1/3}. Becoz, a^3<N. So, a < N^{1/3}. Similarly, for b, c. So it will be fine if we only iterate upto N^{1/3}. First we iterate upto N^{1/3} let’s say with a variable ’ i '.
Then we are left with M=N-i^3. Now we have to express M as sum of 2 perfect cubes. Again we will iterate upto N^{1/3} let’s say with variable ’ j '.
Now we are left with Q=M-j^3. Now, we don’t have to iterate again. We only have to check if Q is a perfect cube or not.
Time Complexity : O(T*N^{2/3})