Problem Of The Day 25 October 2016 — Little Jhool and Brute Force
PROBLEM LINK: Little Jhool and Brute Force
Problem Of The Day 25 October
Little Syed loves brute force. He thinks that brute force can be the solution to any problem in the world. You give him any question, and he’ll have a brute force answer ready for you, almost all the time. His good friend Little Jhool (Like, always!) decides to teach him a lesson, by giving him problems which cannot be solved by brute force, because he wants Syed to learn algorithms.
- Given a number, n, Syed needs to find the number closest to n, though less than n which satisfies Jhool’s swinging theorem.
Jhool’s swinging Theorem: A number n, such that it can be expressed as a sum of two positive algebraic cubes; AND, if that number can be expressed in such a manner in more than one way — it satisfies the theorem.
Now, everyone here on HackerEarth knows how much we hate Little Jhool (No, not really!) — so we want you to help Syed in figuring out Jhool’s queries — once and for all!
Input Format:
The first line contains an integer, t — denoting the number of test cases.
The next t lines will contain, an integer — n — denoting the number which Jhool gives.
Output Format:
You have to print the previous number satisfying the given constraints. If no such previous number exists, print -1.
Constraints:
1 <= t <= 100
1 <= n <= 704977
Explanation
In the first case, since no such number below 100 exists, the result is -1. In the second case, 4104 is the answer because: (4096 + 8 = 4104) or (161616 + 222) and (3375 + 729 = 4104) or (151515 + 999) — that is, there is more than one way in which 4104 can be expressed, satisfying the theorem.
SOLUTION
What i did in this is first i observed the constraints. So the nearest cube is of 89 i.e. only the combinations of cubes of 1 to 89 will be the answers only.Now i used two loops each from 1 to 89 and find all the possible number that can be answers.
By this only 35 numbers are there which satisfy the property of Hardy-Ramanujan Number
Then i stored all these 35 numbers in an array and then created a map where key is the number that satisfy Hardy-Ramanujan Number.
Then at each input case i ran a decreasing loop and check if that number is key. If it is a key then print set answer as that key break the loop (set ans as -1 initially)
CODE
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;int main()
{
//checking the numbers which satisfy the given condition by brute force
/*int i,j,counter=0;
for(i=1728;i<=704977;i++)
{
int count=0;
for(int j=1;j<=89;j++)
{
for(int k=j;k<=89;k++)
{
if(i==(j*j*j)+(k*k*k)) count++;
}
}
if(count>1) counter++;
}
cout<<counter<<endl;*/
//making the array of those numbers
long long int a[]={1729,4104,13832,20683,32832,39312,40033,
46683,64232,65728,110656,110808,134379,149389,
165464,171288,195841,216027,216125,262656,314496,
320264,327763,373464,402597,439101,443889,513000,
513856,515375,525824,558441,593047,684019,704977};//I just write this code to check the max difference between any two numbers/*int max=a[1]-a[0];
for(int i=2;i<35;i++) {
if(a[i]-a[i-1]>max) max=a[i]-a[i-1];
}
cout<<max<<endl;*/
//created a map
map<long long int,bool> mymap;
int i;//mapped the numbers
for(i=0;i<35;i++)
{
mymap[a[i]]=true;
}
int T;
cin>>T;
while(T--) {
long long int x;
cin>>x;
//decreases x till we dont get a number lesser than the x and its a key
// also the maximum difference between two numbers is 10^5 so can be consider as O(1)
while(x!=0)
{
if(mymap.count(x)==1) {
cout<<x<<endl;
break;
}
x--;
}
if(x==0) cout<<"-1"<<endl;
}
}
SOLUTION WILL BE POSTED BY 26-OCT-2016
HAPPY CODING
