Given an array of N integers where N is even. There are two kinds of operations allowed on the array.
- Increase the value of any element A[i] by 1.
- If two adjacent elements in the array are consecutive prime number, delete both the element. That is, A[i] is a prime number and A[i+1] is the next prime number.
The task is to find the minimum number of operation required to remove all the element of the array.
Examples:
Input : arr[] = { 1, 2, 4, 3 }
Output : 5
Minimum 5 operation are required.
1. Increase the 2nd element by 1
{ 1, 2, 4, 3 } -> { 1, 3, 4, 3 }
2. Increase the 3rd element by 1
{ 1, 3, 4, 3 } -> { 1, 3, 5, 3 }
3. Delete the 2nd and 3rd element
{ 1, 3, 5, 3 } -> { 1, 3 }
4. Increase the 1st element by 1
{ 1, 3 } -> { 2, 3 }
5. Delete the 1st and 2nd element
{ 2, 3 } -> { }
Input : arr[] = {10, 12}
Output : 3
To remove numbers, we must transform two numbers to two consecutive primes. How to compute the minimum cost of transforming two numbers a, b to two consecutive primes, where the cost is the number of incrementation of both numbers?
We use sieve to precompute prime numbers and then find the first prime p not greater than a and the first greater than p using array.
Once we have computed two nearest prime numbers, we use Dynamic Programming to solve the problem. Let dp[i][j] be the minimum cost of clearing the subarray A[i, j]. If there are two numbers in the array, the answer is easy to find. Now, for N > 2, try any element at position k > i as a pair for A[i], such that there are even number of elements from A[i, j] between A[i] and A[k]. For a fixed k, the minimum cost of clearing A[i, j], i.e dp[i][j], equals dp[i + 1][k – 1] + dp[k + 1][j] + (cost of transforming A[i] and A[k] into consecutive primes). We can compute the answer by iterating over all possible k.
Below is the implementation of above approach:
C++
// C++ program to count minimum operations// required to remove an array#include<bits/stdc++.h>#define MAX 100005using namespace std;// Return the cost to convert two numbers into// consecutive prime number.int cost(int a, int b, int prev[], int nxt[]){ int sub = a + b; if (a <= b && prev[b-1] >= a) return nxt[b] + prev[b-1] - a - b; a = max(a, b); a = nxt[a]; b = nxt[a + 1]; return a + b - sub;}// Sieve to store next and previous prime// to a number.void sieve(int prev[], int nxt[]){ int pr[MAX] = { 0 }; pr[1] = 1; for (int i = 2; i < MAX; i++) { if (pr[i]) continue; for (int j = i*2; j < MAX; j += i) pr[j] = 1; } // Computing next prime each number. for (int i = MAX - 1; i; i--) { if (pr[i] == 0) nxt[i] = i; else nxt[i] = nxt[i+1]; } // Computing previous prime each number. for (int i = 1; i < MAX; i++) { if (pr[i] == 0) prev[i] = i; else prev[i] = prev[i-1]; }}// Return the minimum number of operation required.int minOperation(int arr[], int nxt[], int prev[], int n){ int dp[n + 5][n + 5] = { 0 }; // For each index. for (int r = 0; r < n; r++) { // Each subarray. for (int l = r-1; l >= 0; l -= 2) { dp[l][r] = INT_MAX; for (int ad = l; ad < r; ad += 2) dp[l][r] = min(dp[l][r], dp[l][ad] + dp[ad+1][r-1] + cost(arr[ad], arr[r], prev, nxt)); } } return dp[0][n - 1] + n/2;}// Driven Programint main(){ int arr[] = { 1, 2, 4, 3 }; int n = sizeof(arr)/sizeof(arr[0]); int nxt[MAX], prev[MAX]; sieve(prev, nxt); cout << minOperation(arr, nxt, prev, n); return 0;} |
Java
// Java program to count minimum operations // required to remove an array class GFG{static final int MAX = 100005;// Return the cost to convert two // numbers into consecutive prime number. static int cost(int a, int b, int prev[], int nxt[]){ int sub = a + b; if (a <= b && prev[b - 1] >= a) { return nxt[b] + prev[b - 1] - a - b; } a = Math.max(a, b); a = nxt[a]; b = nxt[a + 1]; return a + b - sub;}// Sieve to store next and previous // prime to a number. static void sieve(int prev[], int nxt[]){ int pr[] = new int[MAX]; pr[1] = 1; for (int i = 2; i < MAX; i++) { if (pr[i] == 1) { continue; } for (int j = i * 2; j < MAX; j += i) { pr[j] = 1; } } // Computing next prime each number. for (int i = MAX - 2; i > 0; i--) { if (pr[i] == 0) { nxt[i] = i; } else { nxt[i] = nxt[i + 1]; } } // Computing previous prime each number. for (int i = 1; i < MAX; i++) { if (pr[i] == 0) { prev[i] = i; } else { prev[i] = prev[i - 1]; } }}// Return the minimum number // of operation required. static int minOperation(int arr[], int nxt[], int prev[], int n) { int dp[][] = new int[n + 5][n + 5]; // For each index. for (int r = 0; r < n; r++) { // Each subarray. for (int l = r - 1; l >= 0; l -= 2) { dp[l][r] = Integer.MAX_VALUE; for (int ad = l; ad < r; ad += 2) { dp[l][r] = Math.min(dp[l][r], dp[l][ad] + dp[ad + 1][r - 1] + cost(arr[ad], arr[r], prev, nxt)); } } } return dp[0][n - 1] + n / 2;}// Driver Codepublic static void main(String args[]) { int arr[] = {1, 2, 4, 3}; int n = arr.length; int nxt[] = new int[MAX], prev[] = new int[MAX]; sieve(prev, nxt); System.out.println(minOperation(arr, nxt, prev, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program to count minimum # operations required to remove an array MAX = 100005INT_MAX = 10000000# Return the cost to convert two numbers # into consecutive prime number. def cost(a, b, prev, nxt): sub = a + b if (a <= b and prev[b - 1] >= a): return nxt[b] + prev[b - 1] - a - b a = max(a, b) a = nxt[a] b = nxt[a + 1] return a + b - sub# Sieve to store next and previous # prime to a number. def sieve(prev, nxt): pr = [0 for i in range(MAX)] pr[1] = 1 for i in range(1, MAX): if (pr[i]): continue for j in range(i * 2, MAX, i): pr[j] = 1 # Computing next prime each number. for i in range(MAX - 2, -1, -1): if (pr[i] == 0): nxt[i] = i else: nxt[i] = nxt[i + 1] # Computing previous prime each number. for i in range(1, MAX): if (pr[i] == 0): prev[i] = i else: prev[i] = prev[i - 1] # Return the minimum number of # operation required. def minOperation(arr, nxt, prev, n): dp = [[0 for i in range(n + 5)] for i in range(n + 5)] # For each index. for r in range(n): # Each subarray. for l in range(r - 1, -1, -2): dp[l][r] = INT_MAX; for ad in range(l, r, 2): dp[l][r] = min(dp[l][r], dp[l][ad] + dp[ad + 1][r - 1] + cost(arr[ad], arr[r], prev, nxt)) return dp[0][n - 1] + n // 2# Driver Codearr = [1, 2, 4, 3] n = len(arr)nxt = [0 for i in range(MAX)]prev = [0 for i in range(MAX)] sieve(prev, nxt)print(minOperation(arr, nxt, prev, n))# This code is contributed by sahishelangia |
C#
// C# program to count minimum operations // required to remove an array using System;class GFG{static int MAX = 100005;// Return the cost to convert two // numbers into consecutive prime number. static int cost(int a, int b, int[] prev, int[] nxt){ int sub = a + b; if (a <= b && prev[b - 1] >= a) { return nxt[b] + prev[b - 1] - a - b; } a = Math.Max(a, b); a = nxt[a]; b = nxt[a + 1]; return a + b - sub;}// Sieve to store next and previous // prime to a number. static void sieve(int[] prev, int[] nxt){ int[] pr = new int[MAX]; pr[1] = 1; for (int i = 2; i < MAX; i++) { if (pr[i] == 1) { continue; } for (int j = i * 2; j < MAX; j += i) { pr[j] = 1; } } // Computing next prime each number. for (int i = MAX - 2; i > 0; i--) { if (pr[i] == 0) { nxt[i] = i; } else { nxt[i] = nxt[i + 1]; } } // Computing previous prime each number. for (int i = 1; i < MAX; i++) { if (pr[i] == 0) { prev[i] = i; } else { prev[i] = prev[i - 1]; } }}// Return the minimum number // of operation required. static int minOperation(int[] arr, int[] nxt, int[] prev, int n) { int[,] dp = new int[n + 5, n + 5]; // For each index. for (int r = 0; r < n; r++) { // Each subarray. for (int l = r - 1; l >= 0; l -= 2) { dp[l, r] = Int32.MaxValue; for (int ad = l; ad < r; ad += 2) { dp[l, r] = Math.Min(dp[l, r], dp[l, ad] + dp[ad + 1, r - 1] + cost(arr[ad], arr[r], prev, nxt)); } } } return dp[0, n - 1] + n / 2;}// Driver Codepublic static void Main() { int[] arr = {1, 2, 4, 3}; int n = arr.Length; int[] nxt = new int[MAX]; int[] prev = new int[MAX]; sieve(prev, nxt); Console.WriteLine(minOperation(arr, nxt, prev, n));}}// This code is contributed by Mukul Singh |
PHP
<?php // PHP program to count minimum operations// required to remove an array$MAX = 100005; // Return the cost to convert two numbers into// consecutive prime number.function cost($a, $b, &$prev, &$nxt){ $sub = $a + $b; if ($a <= $b && $prev[$b-1] >= $a) return $nxt[$b] + $prev[$b-1] - $a - $b; $a = max($a, $b); $a = $nxt[$a]; $b = $nxt[$a + 1]; return $a + $b - $sub;} // Sieve to store next and previous prime// to a number.function sieve(&$prev, &$nxt){ global $MAX; $pr = array_fill(0,$MAX,NULL); $pr[1] = 1; for ($i = 2; $i < $MAX; $i++) { if ($pr[$i]) continue; for ($j = $i*2; $j < $MAX; $j += $i) $pr[$j] = 1; } // Computing next prime each number. for ($i = $MAX - 1; $i; $i--) { if ($pr[$i] == 0) $nxt[$i] = $i; else $nxt[$i] = $nxt[$i+1]; } // Computing previous prime each number. for ($i = 1; $i < $MAX; $i++) { if ($pr[$i] == 0) $prev[$i] = $i; else $prev[$i] = $prev[$i-1]; }} // Return the minimum number of operation required.function minOperation(&$arr, &$nxt, &$prev, $n){ global $MAX; $dp = array_fill(0,($n + 5),array_fill(0,($n + 5),NULL)); // For each index. for ($r = 0; $r < $n; $r++) { // Each subarray. for ($l = $r-1; $l >= 0; $l -= 2) { $dp[$l][$r] = PHP_INT_MAX; for ($ad = $l; $ad < $r; $ad += 2) $dp[$l][$r] = min($dp[$l][$r], $dp[$l][$ad] + $dp[$ad+1][$r-1] + cost($arr[$ad], $arr[$r], $prev, $nxt)); } } return $dp[0][$n - 1] + $n/2;} // Driven Program$arr = array( 1, 2, 4, 3 );$n = sizeof($arr)/sizeof($arr[0]);$nxt = array_fill(0,$MAX,NULL);$prev = array_fill(0,$MAX,NULL);sieve($prev, $nxt);echo minOperation($arr, $nxt, $prev, $n);return 0;?> |
Javascript
<script>// Javascript program to count minimum operations // required to remove an array let MAX = 100005; // Return the cost to convert two // numbers into consecutive prime number. function cost(a,b,prev,nxt) { let sub = a + b; if (a <= b && prev[b - 1] >= a) { return nxt[b] + prev[b - 1] - a - b; } a = Math.max(a, b); a = nxt[a]; b = nxt[a + 1]; return a + b - sub; } // Sieve to store next and previous // prime to a number. function sieve(prev,nxt) { let pr = new Array(MAX); for(let i=0;i<MAX;i++) { pr[i]=0; } pr[1] = 1; for (let i = 2; i < MAX; i++) { if (pr[i] == 1) { continue; } for (let j = i * 2; j < MAX; j += i) { pr[j] = 1; } } // Computing next prime each number. for (let i = MAX - 2; i > 0; i--) { if (pr[i] == 0) { nxt[i] = i; } else { nxt[i] = nxt[i + 1]; } } // Computing previous prime each number. for (let i = 1; i < MAX; i++) { if (pr[i] == 0) { prev[i] = i; } else { prev[i] = prev[i - 1]; } } } // Return the minimum number // of operation required. function minOperation(arr,nxt,prev,n) { let dp = new Array(n + 5); for(let i=0;i<n+5;i++) { dp[i]=new Array(n+5); for(let j=0;j<n+5;j++) { dp[i][j]=0; } } // For each index. for (let r = 0; r < n; r++) { // Each subarray. for (let l = r - 1; l >= 0; l -= 2) { dp[l][r] = Number.MAX_VALUE; for (let ad = l; ad < r; ad += 2) { dp[l][r] = Math.min(dp[l][r], dp[l][ad] + dp[ad + 1][r - 1] + cost(arr[ad], arr[r], prev, nxt)); } } } return dp[0][n - 1] + n / 2; } // Driver Code let arr=[1, 2, 4, 3]; let n = arr.length; let nxt=new Array(MAX); let prev=new Array(MAX); sieve(prev, nxt); document.write(minOperation(arr, nxt, prev, n)); // This code is contributed by rag2127 </script> |
Output
5
Time Complexity: O(N3).
Space Complexity: O(N)
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!