#include <bits/stdc++.h>
using namespace std;
int ans[1000000];
//returns the minimum prime numbers neede to form x
int func(int x)
{
if(x==2 || x==3 || x==5 || x==7)
{
ans[x]=1;
return ans[x];
}
if(x<=1)
{
return 0;
}
int a7=ans[x-7]!=-1?ans[x-7]:func(x-7);
int t7=a7>=1?a7:INT_MAX;
int a5=ans[x-5]!=-1?ans[x-5]:func(x-5);
int t5=a5>=1?a5:INT_MAX;
int a3=ans[x-3]!=-1?ans[x-3]:func(x-3);
int t3=a3>=1?a3:INT_MAX;
int a2=ans[x-2]!=-1?ans[x-2]:func(x-2);
int t2=a2>=1?a2:INT_MAX;
ans[x]=1+min(t7,min(t5,min(t3,t2)));
if(ans[x]!=INT_MAX)
return ans[x];
else
{
ans[x]=0;
return ans[x];
}
}
int main()
{
memset(ans,-1,sizeof(ans));
ans[1]=0;
ans[0]=0;
int t;
cin>>t;
while(t--)
{
int x;
cin>>x;
int final=func(x);
if(final==0)
cout<<"-1";
else
cout<<final;
cout<<"\n";
}
}
- Problem Description
February Easy Challenge 2015 is underway. Hackerearth welcomes you all and hope that all you awesome coders have a great time. So without wasting much of the time let’s begin the contest.
Prime Numbers have always been one of the favourite topics for problem setters.
Aishwarya is a mathematics student at the Department of Mathematics and Computing, California. Her teacher recently gave her an intriguing assignment with only a single question. The question was to find out the minimum number of single digit prime numbers which when summed equals a given number X.
Input:
The first line contains T denoting the number of test cases. Each of the next T lines contains a single integer X.
Output:
Print the minimum number required. If it is not possible to obtain X using single digit prime numbers, output -1.
Constraints:
1<=T<=100
1<=X<=10^6
- Test Case 1
Input (stdin)4
7
10
14
11
Expected Output1
2
2
3
- Test Case 2
Input (stdin)3
5688
11126
17529
Expected Output814
1590
2505
No comments:
Post a Comment