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.