You are given an integer N.You have to use minimum no. of primes less than 1000 that sum equals to N. If it is not possible to produce a sum, print -1. Otherwise, output minimum primes required.
for example:
N=6
output:
2
explaination: 3+3=6
N=7666
output:
8
Note: This question was asked in yesterday’s interview bit academy test.
You need to generate prime numbers till 1000.
Then treat this prime numbers has coins with value equal to that prime number.
Preform “Coin change with minimum coins” problem logic on these prime value coins ans number N.
suppose there is no constraint on which prime we can use.
Then if N is even:
if N is 2 then answer is 1 (since 2 itself is prime)
if N is not 2 then answer is 2 (because as per Goldbach's conjecture any even > 2 can be expressed as sum of two primes.)
if N is odd :
if N is prime answer is 1
else if (N-2) is prime answer is 2
else answer is 3 ( Because (N-anyprime) =even which can be expressed as sum of two primes so (N-p1)=p2+p3 : N=p1+p2+p3)
NOW we have given constraint that we have to use primes less than 1000:
997 is largest prime less than 1000 so we have , so to minimize number of prime we have to use we 997 will come floor(N/997) time now N becomes N= Nmod 997 now minimum primes required can be obtained by above algo .
TO sum up Let F(N ) be the function which gives Minimum primes less than 1000 required to produce sum N and G(N) gives Minimum primes required to produce sum N
Well, this problem is a mix of two basic concepts.
1.) sieve of eratosthenes.(for finding primes till 1000)
2.) DP- coin change problem.(for finding minimum primes to make n)
You literally have to combine them. thats it!
So, You could easily search both of them online and understand them.
I tried to code the problem. Please check if it’s correct
#include <bits/stdc++.h>
using namespace std;
#define fastio std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test int t;cin>>t;while(t--)
vector<int> prime;
void precomp_prime() // Sieve of EraTHANOS O(x*log(log(x))) x is till where you want the primes
{
bool isprime[1001];
memset(isprime,true,sizeof(isprime));
for(int i=2;i*i<1001;i++)
{
if(isprime[i]==true)
{
for(int j=i*i;j<1001;j+=i)
isprime[j]=false;
}
}
for(int i=2;i<1001;i++)
{
if(isprime[i])
prime.push_back(i);
}
}
int minCoins(vector<int> coins, int m, int V) // dp=coin change O(mV)
{
int table[V+1];
table[0] = 0;
for (int i=1; i<=V; i++)
table[i] = INT_MAX;
for (int i=1; i<=V; i++)
{
for (int j=0; j<m; j++)
if (coins[j] <= i)
{
int sub_res = table[i-coins[j]];
if (sub_res != INT_MAX && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
return table[V];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("inp.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
fastio;
precomp_prime();
test{
/*for(int i=0;i<prime.size();i++)
cout<<prime[i]<<" ";*/
int n;cin>>n;
cout<<minCoins(prime,prime.size(),n)<<"\n";
}
return 0;
}