Question Name:LET’S BEGIN!

#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

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro