Insert minimum number in array so that sum of array becomes prime
Given an array of n integers. Find minimum number to be inserted in array, so that sum of all elements of array becomes prime. If sum is already prime, then return 0.
Examples :
Input : arr[] = { 2, 4, 6, 8, 12 }
Output : 5
Input : arr[] = { 3, 5, 7 }
Output : 0
Naive approach: The simplest approach to solve this problem is to first find the sum of array elements. Then check if this sum is prime or not, if sum is prime return zero otherwise find prime number just greater than this sum. We can find prime number greater than sum by checking if a number is prime or not from (sum+1) until we find a prime number. Once a prime number just greater than sum is found, return difference of sum and this prime number.
Below is implementation of above idea:
C++
// C++ program to find minimum number to// insert in array so their sum is prime#include <bits/stdc++.h>using namespace std;// function to check if a// number is prime or notbool isPrime(int n){ // Corner case if (n <= 1) return false; // Check from 2 to n - 1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Find prime number // greater than a numberint findPrime(int n){ int num = n + 1; // find prime greater than n while (num) { // check if num is prime if (isPrime(num)) return num; // increment num num = num + 1; } return 0;}// To find number to be added // so sum of array is primeint minNumber(int arr[], int n){ int sum = 0; // To find sum of array elements for (int i = 0; i < n; i++) sum += arr[i]; // if sum is already prime // return 0 if (isPrime(sum)) return 0; // To find prime number // greater than sum int num = findPrime(sum); // Return difference of // sum and num return num - sum;}// Driver codeint main(){ int arr[] = { 2, 4, 6, 8, 12 }; int n = sizeof(arr) / sizeof(arr[0]); cout << minNumber(arr, n); return 0;} |
Java
// Java program to find minimum number to// insert in array so their sum is primeclass GFG{ // function to check if a // number is prime or not static boolean isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n - 1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Find prime number // greater than a number static int findPrime(int n) { int num = n + 1; // find prime greater than n while (num > 0) { // check if num is prime if (isPrime(num)) return num; // increment num num = num + 1; } return 0; } // To find number to be added // so sum of array is prime static int minNumber(int arr[], int n) { int sum = 0; // To find sum of array elements for (int i = 0; i < n; i++) sum += arr[i]; // if sum is already prime // return 0 if (isPrime(sum)) return 0; // To find prime number // greater than sum int num = findPrime(sum); // Return difference of // sum and num return num - sum; } // Driver Code public static void main(String[]args) { int arr[] = { 2, 4, 6, 8, 12 }; int n = arr.length; System.out.println(minNumber(arr, n)); }} // This code is contributed by Azkia Anam. |
Python3
# Python3 program to find minimum number to# insert in array so their sum is prime# function to check if a# number is prime or notdef isPrime(n): # Corner case if n <= 1: return False # Check from 2 to n - 1 for i in range(2, n): if n % i == 0: return False return True# Find prime number # greater than a numberdef findPrime(n): num = n + 1 # find prime greater than n while (num): # check if num is prime if isPrime(num): return num # Increment num num += 1 return 0# To find number to be added# so sum of array is primedef minNumber(arr): s = 0 # To find sum of array elements for i in range(0, len(arr)): s += arr[i] # If sum is already prime # return 0 if isPrime(s) : return 0 # To find prime number # greater than sum num = findPrime(s) # Return difference of sum and num return num - s# Driver codearr = [ 2, 4, 6, 8, 12 ]print (minNumber(arr))# This code is contributed by Sachin Bisht |
C#
// C# program to find minimum number to// insert in array so their sum is primeusing System;class GFG{ // function to check if a // number is prime or not static bool isPrime(int n) { // Corner case if (n <= 1) return false; // Check from 2 to n - 1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Find prime number // greater than a number static int findPrime(int n) { int num = n + 1; // find prime greater than n while (num > 0) { // check if num is prime if (isPrime(num)) return num; // increment num num = num + 1; } return 0; } // To find number to be added // so sum of array is prime static int minNumber(int []arr, int n) { int sum = 0; // To find sum of array elements for (int i = 0; i < n; i++) sum += arr[i]; // if sum is already prime // return 0 if (isPrime(sum)) return 0; // To find prime number // greater than sum int num = findPrime(sum); // Return difference of sum and num return num - sum; } // Driver Code public static void Main() { int []arr = { 2, 4, 6, 8, 12 }; int n = arr.Length; Console.Write(minNumber(arr, n)); }} // This code is contributed by nitin mittal |
PHP
<?php// PHP program to find minimum number to// insert in array so their sum is prime// function to check if a// number is prime or notfunction isPrime($n){ // Corner case if ($n <= 1) return false; // Check from 2 to n - 1 for ($i = 2; $i < $n; $i++) if ($n % $i == 0) return false; return true;}// Find prime number // greater than a numberfunction findPrime($n){ $num = $n + 1; // find prime greater than n while ($num) { // check if num is prime if (isPrime($num)) return $num; // increment num $num = $num + 1; } return 0;}// To find number to be added // so sum of array is primefunction minNumber($arr, $n){ $sum = 0; // To find sum of array elements for ($i = 0; $i < $n; $i++) $sum += $arr[$i]; // if sum is already prime // return 0 if (isPrime($sum)) return 0; // To find prime number // greater than sum $num = findPrime($sum); // Return difference of // sum and num return $num - $sum;} // Driver Code $arr = array(2, 4, 6, 8, 12); $n = sizeof($arr); echo minNumber($arr, $n);// This code is contributed by nitin mittal?> |
Javascript
<script>// Javascript program to find minimum number to// insert in array so their sum is prime // function to check if a // number is prime or not function isPrime(n) { // Corner case if (n <= 1) return false; // Check from 2 to n - 1 for (let i = 2; i < n; i++) if (n % i == 0) return false; return true; } // Find prime number // greater than a number function findPrime(n) { let num = n + 1; // find prime greater than n while (num > 0) { // check if num is prime if (isPrime(num)) return num; // increment num num = num + 1; } return 0; } // To find number to be added // so sum of array is prime function minNumber(arr,n) { let sum = 0; // To find sum of array elements for (let i = 0; i < n; i++) sum += arr[i]; // if sum is already prime // return 0 if (isPrime(sum)) return 0; // To find prime number // greater than sum let num = findPrime(sum); // Return difference of // sum and num return num - sum; } // Driver Code let arr=[2, 4, 6, 8, 12 ]; let n = arr.length; document.write(minNumber(arr, n)); //This code is contributed by avanitrachhadiya2155 </script> |
Output
5
Time Complexity: O( N2 )
Efficient Approach: We can optimize the above approach by efficiently pre calculating a large boolean array to check if a number is prime or not using sieve of eratosthenes. Once all prime number are generated, find prime number just greater than sum and return the difference between them.
Below is the implementation of this approach:
C++
// C++ program to find minimum number to// insert in array so their sum is prime#include <bits/stdc++.h>using namespace std;#define MAX 100005// Array to store primesbool isPrime[MAX];// function to calculate primes // using sieve of eratosthenesvoid sieveOfEratostheneses(){ memset(isPrime, true, sizeof(isPrime)); isPrime[1] = false; for (int i = 2; i * i < MAX; i++) { if (isPrime[i]) { for (int j = 2 * i; j < MAX; j += i) isPrime[j] = false; } }}// Find prime number // greater than a numberint findPrime(int n){ int num = n + 1; // To return prime number // greater than n while (num) { // check if num is prime if (isPrime[num]) return num; // increment num num = num + 1; } return 0;}// To find number to be added // so sum of array is primeint minNumber(int arr[], int n){ // call sieveOfEratostheneses // to calculate primes sieveOfEratostheneses(); int sum = 0; // To find sum of array elements for (int i = 0; i < n; i++) sum += arr[i]; if (isPrime[sum]) return 0; // To find prime number // greater then sum int num = findPrime(sum); // Return difference of // sum and num return num - sum;}// Driver Codeint main(){ int arr[] = { 2, 4, 6, 8, 12 }; int n = sizeof(arr) / sizeof(arr[0]); cout << minNumber(arr, n); return 0;} |
Java
// Java program to find minimum number to// insert in array so their sum is primeclass GFG{static int MAX = 100005;// Array to store primesstatic boolean[] isPrime = new boolean[MAX];// function to calculate primes // using sieve of eratosthenesstatic void sieveOfEratostheneses(){ isPrime[1] = true; for (int i = 2; i * i < MAX; i++) { if (!isPrime[i]) { for (int j = 2 * i; j < MAX; j += i) isPrime[j] = true; } }}// Find prime number greater // than a numberstatic int findPrime(int n){ int num = n + 1; // To return prime number // greater than n while (num > 0) { // check if num is prime if (!isPrime[num]) return num; // increment num num = num + 1; } return 0;}// To find number to be added // so sum of array is primestatic int minNumber(int arr[], int n){ // call sieveOfEratostheneses // to calculate primes sieveOfEratostheneses(); int sum = 0; // To find sum of array elements for (int i = 0; i < n; i++) sum += arr[i]; if (!isPrime[sum]) return 0; // To find prime number // greater then sum int num = findPrime(sum); // Return difference of // sum and num return num - sum;}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 4, 6, 8, 12 }; int n = arr.length; System.out.println(minNumber(arr, n));}}// This code is contributed by mits |
Python3
# Python3 program to find minimum number to# insert in array so their sum is primeisPrime = [1] * 100005# function to calculate prime # using sieve of eratosthenesdef sieveOfEratostheneses(): isPrime[1] = False i = 2 while i * i < 100005: if(isPrime[i]): j = 2 * i while j < 100005: isPrime[j] = False j += i i += 1 return# Find prime number# greater than a numberdef findPrime(n): num = n + 1 # find prime greater than n while(num): # check if num is prime if isPrime[num]: return num # Increment num num += 1 return 0# To find number to be added # so sum of array is primedef minNumber(arr): # call sieveOfEratostheneses to # calculate primes sieveOfEratostheneses() s = 0 # To find sum of array elements for i in range(0, len(arr)): s += arr[i] # If sum is already prime # return 0 if isPrime[s] == True: return 0 # To find prime number # greater than sum num = findPrime(s) # Return difference of # sum and num return num - s# Driver codearr = [ 2, 4, 6, 8, 12 ]print (minNumber(arr))# This code is contributed by Sachin Bisht |
C#
// C# program to find minimum number to// insert in array so their sum is primeclass GFG{static int MAX = 100005;// Array to store primesstatic bool[] isPrime = new bool[MAX];// function to calculate primes // using sieve of eratosthenesstatic void sieveOfEratostheneses(){ isPrime[1] = true; for (int i = 2; i * i < MAX; i++) { if (!isPrime[i]) { for (int j = 2 * i; j < MAX; j += i) isPrime[j] = true; } }}// Find prime number greater // than a numberstatic int findPrime(int n){ int num = n + 1; // To return prime number // greater than n while (num > 0) { // check if num is prime if (!isPrime[num]) return num; // increment num num = num + 1; } return 0;}// To find number to be added // so sum of array is primestatic int minNumber(int[] arr, int n){ // call sieveOfEratostheneses // to calculate primes sieveOfEratostheneses(); int sum = 0; // To find sum of array elements for (int i = 0; i < n; i++) sum += arr[i]; if (!isPrime[sum]) return 0; // To find prime number // greater then sum int num = findPrime(sum); // Return difference of // sum and num return num - sum;}// Driver Codepublic static void Main(){ int[] arr = { 2, 4, 6, 8, 12 }; int n = arr.Length; System.Console.WriteLine(minNumber(arr, n));}}// This code is contributed by mits |
PHP
<?php// PHP program to find minimum number to // insert in array so their sum is prime $MAX =100005; // function to calculate primes // using sieve of eratosthenesfunction sieveOfEratostheneses() { $isPrime = array_fill(true,$MAX, NULL); $isPrime[1] = false; for ($i = 2; $i * $i < $MAX; $i++) { if ($isPrime[$i]) { for ($j = 2 * $i; $j < $MAX; $j += $i) $isPrime[$j] = false; } } } // Find prime number // greater than a number function findPrime($n) { $num = $n + 1; // To return prime number // greater than n while ($num) { // check if num is prime if ($isPrime[$num]) return $num; // increment num $num = $num + 1; } return 0; } // To find number to be added // so sum of array is prime function minNumber(&$arr, $n) { // call sieveOfEratostheneses // to calculate primes sieveOfEratostheneses(); $sum = 0; // To find sum of array elements for ($i = 0; $i < $n; $i++) $sum += $arr[$i]; if ($isPrime[$sum]) return 0; // To find prime number // greater then sum $num = findPrime($sum); // Return difference of // sum and num return $num - $sum; } // Driver Code $arr = array ( 2, 4, 6, 8, 12 ); $n = sizeof($arr) / sizeof($arr[0]); echo minNumber($arr, $n); return 0; ?> |
Javascript
<script>// Javascript program to find minimum number to// insert in array so their sum is primelet MAX = 100005; // Array to store primeslet isPrime = new Array(MAX).fill(0); // function to calculate primes // using sieve of eratosthenesfunction sieveOfEratostheneses(){ isPrime[1] = true; for (let i = 2; i * i < MAX; i++) { if (!isPrime[i]) { for (let j = 2 * i; j < MAX; j += i) isPrime[j] = true; } }} // Find prime number greater // than a numberfunction findPrime(n){ let num = n + 1; // To return prime number // greater than n while (num > 0) { // check if num is prime if (!isPrime[num]) return num; // increment num num = num + 1; } return 0;} // To find number to be added // so sum of array is primefunction minNumber(arr, n){ // call sieveOfEratostheneses // to calculate primes sieveOfEratostheneses(); let sum = 0; // To find sum of array elements for (let i = 0; i < n; i++) sum += arr[i]; if (!isPrime[sum]) return 0; // To find prime number // greater then sum let num = findPrime(sum); // Return difference of // sum and num return num - sum;}// driver program let arr = [ 2, 4, 6, 8, 12 ]; let n = arr.length; document.write(minNumber(arr, n));// This code is contributed by code_hunt.</script> |
Output
5
Time Complexity: O(N log(log N))
This article is contributed by nuclode. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
