Question

Amazon WoW | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-42

Answer 1

#include <bits/stdc++.h>

using namespace std;

vector<int> primes(int n, int count)

{

    vector<int> prime_list;

    if (n < 2)

        return prime_list;

    vector<int> seive(n + 1, 1);

    seive[0] = 0, seive[1] = 0;

    for (int num = 2; num <= n; num++)

    {

        if (seive[num] == 0)

            continue;

        for (int j = num * num; j <= n; j += num)

        {

            seive[j] = 0;

        }

    }

    for (int i = 2; i < n; i++)

    {

        if (count == 0)

            break;

        if (seive[i] == 1 && count > 0)

        {

            prime_list.push_back(i);

            count--;

        }

    }

 

    return prime_list;

}

int helper(int d, vector<int> &prime_list, vector<int> &dp)

{

    if (d == 0)

        return 0;

    if (d < 0)

        return INT_MAX;

    if (dp[d] != -1)

        return dp[d];

    int steps = INT_MAX;

    for (int i = 0; i < prime_list.size(); i++)

    {

        steps = min(steps, helper(d - prime_list[i], prime_list, dp));

    }

    if (steps == INT_MAX)

        dp[d] = INT_MAX;

    else

        dp[d] = steps + 1;

    return dp[d];

}

int main()

{

    int d, k;

    cin >> d >> k;

    vector<int> dp(d + 1, -1);

    vector<int> prime_list = primes(d, k);

    int ans = helper(d, prime_list, dp);

    if (ans == INT_MAX)

        cout << -1 << endl;

    else

        cout << ans << endl;

}

Answer 2

Question asked :