Given an array of n integers. Find the minimum positive number to be inserted in array, so that sum of all elements of array becomes prime.

Example 1:

Input:
N=5
arr = {2, 4, 6, 8, 12}
Output:  
5
Explanation: 
The sum of the array is 32 ,we can add 5 to this to make it 37 which is a prime number.

Example 2:

Input:
N=3
arr = {1, 5, 7}
Output:  
0 
Explanation: 
The sum of the array is 13 which is already prime.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function minNumber() that takes array arr and integer N as input parameters and returns the minimum positive number to be inserted in the array so as to make it’s sum a prime number.

Expected Time Complexity: O(N log(log N))
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ N ≤ 105
1 ≤ sum of all elements ≤ 106

Explanation:

Here given array size and integer array as input.

sum the all array values and check if the sum is prime return 0 else add extra value to make the sum as prime and return the minimum number is added to make the sum as prime.

Approach 1:

Step 1:

sum the all the array values. after sum call the makePrime() method.

Step 2:

Inside makePrime(int num)

check the num is prime or not by calling the isPrime().

While: when we don’t the iteration count we can go with the while loop.

if number is prime return by the isPrime() (!true) -> false terminate the loop and return the prime number.

else not a prime then increment the num++ value by one. again call the isPrime() for every increment.

Step 4:

How to check A number is prime or not.

For detailed view of number is prime or not check below link👇

https://sirishachallagiri.hashnode.dev/number-is-prime-or-not

CODE:

public class MakePrimeGFG {
  public static void main(String[] args) {
    int[] arr = {2, 4, 6, 8, 12};
    int N = 5;

    System.out.println(minNumber(arr, N));
  }

  //step 1
  public static int minNumber(int arr[], int N)
  {
    int sum=0;
    for(int i=0;i<arr.length;i++){
      sum+=arr[i];
    }

    return makePrime(sum)-sum; //eg: 37-32 = 5
  }

  //step 2
  public static int makePrime(int num)
  {    
    while(!isPrime(num)){
      num++;
    }
    return num;
  }

  //check prime or not
  public static boolean isPrime(int num){
    if(num <= 1){
      return false;
    }

    for(int i=2;i*i<=num;i++){
      if(num%i==0){
        return false;
      }
    }
    return true;
  }
}

Output:

5

5 is added to 32 to make the number is prime.

minimum number is added to make the number is prime.

Approach 2: Recursion

In step 2 recursion is applied.

public static int makePrime(int num)
  {    
    if(isPrime(num)){
      return num;
    }
    else{
      num++;
      return makePrime(num);
    }
  }

without using the while loop used recursion.

if number is prime return number.

else increment the number and all the method itself and check isPrime() if true return and increment same process will continue until the number is prime.

CODE:

public class MakePrimeGFG {
  public static void main(String[] args) {
    int[] arr = {2, 4, 6, 8, 12};
    int N = 5;

    System.out.println(minNumber(arr, N));
  }

  //step 1
  public static int minNumber(int arr[], int N)
  {
    int sum=0;
    for(int i=0;i<arr.length;i++){
      sum+=arr[i];
    }

    return makePrime(sum)-sum;
  }

  //step 2
  public static int makePrime(int num)
  {    
    if(isPrime(num)){
      return num;
    }
    else{
      num++;
      return makePrime(num);
    }
  }

  public static boolean isPrime(int num){
    if(num <= 1){
      return false;
    }

    for(int i=2;i*i<=num;i++){
      if(num%i==0){
        return false;
      }
    }
    return true;
  }
}

Output:

5

Problem Link: https://www.geeksforgeeks.org/problems/transform-to-prime4635/1

Thank you for reading.

Happy Coding :)