Java Code for PrimeConstruction (TCS Codevita) | PrepInsta
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.
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”.
Print single integer p if such a p exists, else print “None”.
Time Limit : 1 secs
Example 1 :
Input :
4
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.
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 :
4
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”.
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”.
Java
Java
Run
import java.util.*;
public class Main {
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
public static int findlcm(ArrayList< Integer> arr, int n) {
int ans = arr.get(0);
for (int i = 1; i < n; i++)
ans = (((arr.get(i) * ans)) / (gcd(arr.get(i), ans)));
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
ArrayList< Integer> v = new ArrayList<>();
for (int i = 0; i < n; i++) {
int t = scanner.nextInt();
v.add(t);
}
int a = Collections.min(v);
int index = v.indexOf(a);
if (index != -1)
v.remove(index);
int res = findlcm(v, n - 1);
System.out.println(res + a);
}
}
