Prime Sum

Moderate

0/80

0 upvote

Problem statement

You are given an array of n integers. Your task is to find the minimum non-negative integer that must be added to the array to make the total sum of all its elements a prime number.

The process is as follows:

1) Calculate the sum of all elements currently in the array.
2) Check if this sum is a prime number.
3) If the sum is already prime, no number needs to be added, so the answer is 0.
4) If the sum is not prime, find the smallest prime number that is strictly greater than the current sum. The difference between this next prime and the current sum is the minimum number you need to add.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of elements in the array.

The second line contains N space-separated integers, representing the elements of the array.

Output Format:

Your function should return a single integer.

Note:

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The number 1 is not a prime number.

The sum of the array can be large, so you will need an efficient way to find the next prime number.

Sample Input 1:

5
2 4 6 8 1

Sample Output 1:

Explanation for Sample 1:

The sum of the array elements is 2 + 4 + 6 + 8 + 1 = 21.
21 is not a prime number (divisible by 3 and 7).
The next prime number greater than 21 is 23.
The number to be added is 23 - 21 = 2

Sample Input 2:

3
1 5 7

Sample Output 2:

Explanation for Sample 2:

The sum of the array elements is 1 + 5 + 7 = 13.
13 is a prime number.
Since the sum is already prime, the number to be added is 0.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 1000
1 <= array element <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Prime Sum

Console