Conversation with Merlin [email protected] · Tue Nov 21 2023

Ronny's confidence level (C) is O. You have a series of K exercises, each of which increases Ronny's confidence by P[K] units, respectively. P[K] is a set of K prime numbers, [2, 3, 5, 7,1....]

Ronny practices exactly 1 exercise each day. The same exercise can be practiced over and over again. Your task is to find and return the minimum number of days it will take for his confidence level to reach D exactly.

Input Specific

input1: An integer representing final confidence level.

input2: An integer K representing the total different number of exercises

Output Specification:

Return the minimum number of days required to achieve the target. If not possible, output-1.

Example 1:

input1: 10

input2: 1

Output: 5

TEST CASE INFORMATION

Input

11,3

Expected Output

3

Please complete below the function and write the correct code in cpp

int minDays(int input1, int input2){ // Read only region end

// Write code and remove the below exception.

throw "Function minDays(int inputi, int input2) not in

}

Here's the C++ code to solve the given problem:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int minDays(int input1, int input2) {
    vector<int> primeNumbers;
    int i = 2;
    while (primeNumbers.size() < input2) {
        if (isPrime(i)) {
            primeNumbers.push_back(i);
        }
        i++;
    }

    unordered_set<int> visited;
    queue<pair<int int>> q;
    q.push({0, 0});
    visited.insert(0);

    while (!q.empty()) {
        int days = q.front().first;
        int confidence = q.front().second;
        q.pop();

        if (confidence == input1) {
            return days;
        }

        for (int p : primeNumbers) {
            int newConfidence = confidence + p;
            if (newConfidence <= input1 && visited.find(newConfidence) == visited.end()) {
                visited.insert(newConfidence);
                q.push({days + 1, newConfidence});
            }
        }
    }

    return -1;
}

// Example usage
int main() {
    int result = minDays(10, 1);
    cout << result;  // Output: 5
    return 0;
}

In this code, we first generate the list of the first K prime numbers. Then, we perform a breadth-first search (BFS) to find the minimum number of days required to reach the target confidence level. The BFS algorithm explores all possible paths through the exercise choices and terminates when the target confidence level is reached, or all possible exercises have been exhausted without reaching the target. If the target can't be reached, the function returns -1.