C++ Code for PrimeConstruction (TCS Codevita) | PrepInsta

October 17, 2023

PrimeConstruction

TCS CodeVita is a coding competition organized by TCS every year, in search of world’s best coder. This is a global level coding competition in which coders from all around the world compete for the title of World’s Best Coder. PrimeConstruction is one of the sample problem of this year TCS CodeVita season 11 competition.

Problem Description

Question -: A math game is introduced in a school competition to test the skills of students. The game deals with Prime numbers.
The game rules are as follows:

From the given set of distinct natural numbers as input, consider the smallest natural number as q.
Your task is to compute the smallest prime number (p) such that when p is divided by all the distinct numbers in the input, except q, should result q as the remainder.

Constraints :

1 < n < 11
p < 10 ^ 10

Input :
Input consists of n+1 number of distinct natural numbers separated by spaces.

Output :
Print single integer p if such a p exists, else print “None”.

Time Limit : 1 secs

Example 1 :
Input :

3 4 5 1
Output : 61
Explanation : Here the n+1 numbers are 3, 4, 5 and 1 where q=1 (the least of the numbers)
The smallest number that leaves remainder 1 when divided by 3, 4 and 5 is 61 and is prime. Hence, output is 61.

Example 2 :
Input :

3 4 5 2
Output : None
Explanation : Here q=2. Any number that when divided by 4 leaving remainder 2 must be an even number e.g., 6, 10, 14 etc. Hence it can’t be prime. Hence, output is “None”.

C++

Run

#include< bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
// Returns LCM of array elements
int findlcm(vector< int>arr, int n)
{
    // Initialize result
    int ans = arr[0];
    // ans contains LCM of arr[0], ..arr[i]
    // after i'th iteration,
    for (int i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));
    return ans;
}
int main(){
    int n;
    cin>>n;
    vector< int>v;
    for(int i=0;i< n;i++){
        int t;
        cin>>t;
        v.push_back(t);
    }
    int a = *min_element(v.begin(), v.end());
   auto it = find(v.begin(), v.end(), a);
    if (it != v.end())
        v.erase(it);
    int res;
    res = findlcm(v, n-1);
    cout<< res+a;
}