Given an array arr[], the task is to maximize the length of increasing subsequence by replacing elements to greater or smaller prime number to the element.
Examples:
Input: arr[] = {4, 20, 6, 12}
Output: 3
Explanation:
Modify the array arr[] as {3, 19, 5, 11} to maximize answer,
where {3, 5, 11} is longest increasing subsequence with length as 3.Input: arr[] = {30, 43, 42, 19}
Output: 2
Explanation:
Modify the array arr[] as {31, 43, 42, 19} to maximize answer,
where {31, 43} is longest increasing subsequence with length as 2.
Approach: The idea is to replace each element with a smaller prime number and next prime number and form another sequence over which we can apply the standard Longest increasing subsequence algorithm. Keeping a greater prime number before the smaller prime number guarantees that both of them cannot exist in any increasing sequence simultaneously.
Below is the implementation of the above approach:
C++14
// C++ program for above approach #include<bits/stdc++.h> using namespace std; // Function to check if a // number is prime or not bool isprime( int n) { if (n < 2) return false ; for ( int i = 2; i * i <= n; i++) if (n % i == 0) return false ; return true ; } // Function to find nearest // greater prime of given number int nextprime( int n) { while (!isprime(n)) n++; return n; } // Function to find nearest // smaller prime of given number int prevprime( int n) { if (n < 2) return 2; while (!isprime(n)) n--; return n; } // Function to return length of longest // possible increasing subsequence int longestSequence(vector< int > A) { // Length of given array int n = A.size(); int M = 1; // Stores increasing subsequence vector< int > l; // Insert first element prevprime l.push_back(prevprime(A[0])); // Traverse over the array for ( int i = 1; i < n; i++) { // Current element int x = A[i]; // Check for contribution of // nextprime and prevprime // to the increasing subsequence // calculated so far for ( int p :{ nextprime(x), prevprime(x) }) { int low = 0; int high = M - 1; // Reset first element of list, // if p is less or equal if (p <= l[0]) { l[0] = p; continue ; } // Finding appropriate position // of Current element in l while (low < high) { int mid = (low + high + 1) / 2; if (p > l[mid]) low = mid; else high = mid - 1; } // Update the calculated position // with Current element if (low + 1 < M) l[low + 1] = p; // Otherwise add current element // in L and increase M // as list size increases else { l.push_back(p); M++; } } } // Return M as length of possible // longest increasing sequence return M; } // Driver Code int main() { vector< int > A = { 4, 20, 6, 12 }; // Function call cout << (longestSequence(A)); } // This code is contributed by mohit kumar 29 |
Java
// Java Program for above approach import java.util.*; import java.lang.*; class GFG { // Function to check if a // number is prime or not static boolean isprime( int n) { if (n < 2 ) return false ; for ( int i = 2 ; i * i <= n; i++) if (n % i == 0 ) return false ; return true ; } // Function to find nearest // greater prime of given number static int nextprime( int n) { while (!isprime(n)) n++; return n; } // Function to find nearest // smaller prime of given number static int prevprime( int n) { if (n < 2 ) return 2 ; while (!isprime(n)) n--; return n; } // Function to return length of longest // possible increasing subsequence static int longestSequence( int [] A) { // Length of given array int n = A.length; int M = 1 ; // Stores increasing subsequence List<Integer> l = new ArrayList<>(); // Insert first element prevprime l.add(prevprime(A[ 0 ])); // Traverse over the array for ( int i = 1 ; i < n; i++) { // Current element int x = A[i]; // Check for contribution of // nextprime and prevprime // to the increasing subsequence // calculated so far for ( int p : new int [] { nextprime(x), prevprime(x) }) { int low = 0 ; int high = M - 1 ; // Reset first element of list, // if p is less or equal if (p <= l.get( 0 )) { l.set( 0 , p); continue ; } // Finding appropriate position // of Current element in l while (low < high) { int mid = (low + high + 1 ) / 2 ; if (p > l.get(mid)) low = mid; else high = mid - 1 ; } // Update the calculated position // with Current element if (low + 1 < M) l.set(low + 1 , p); // Otherwise add current element // in L and increase M // as list size increases else { l.add(p); M++; } } } // Return M as length of possible // longest increasing sequence return M; } // Driver Code public static void main(String[] args) { int [] A = { 4 , 20 , 6 , 12 }; // Function call System.out.println( longestSequence(A)); } } |
Python3
# Python3 Program for # the above approach #Function to check if a # number is prime or not def isprime(n): if (n < 2 ): return False i = 2 while i * i < = n: if (n % i = = 0 ): return False i + = 2 return True # Function to find nearest # greater prime of given number def nextprime(n): while ( not isprime(n)): n + = 1 return n # Function to find nearest # smaller prime of given number def prevprime(n): if (n < 2 ): return 2 while ( not isprime(n)): n - = 1 return n # Function to return length of longest # possible increasing subsequence def longestSequence(A): # Length of given array n = len (A) M = 1 # Stores increasing subsequence l = [] # Insert first element prevprime l.append(prevprime(A[ 0 ])) # Traverse over the array for i in range ( 1 , n): # Current element x = A[i] # Check for contribution of # nextprime and prevprime # to the increasing subsequence # calculated so far for p in [nextprime(x), prevprime(x)]: low = 0 high = M - 1 # Reset first element of list, # if p is less or equal if (p < = l[ 0 ]): l[ 0 ] = p continue # Finding appropriate position # of Current element in l while (low < high) : mid = (low + high + 1 ) / / 2 if (p > l[mid]): low = mid else : high = mid - 1 # Update the calculated position # with Current element if (low + 1 < M): l[low + 1 ] = p # Otherwise add current element # in L and increase M # as list size increases else : l.append(p) M + = 1 # Return M as length of possible # longest increasing sequence return M # Driver Code if __name__ = = "__main__" : A = [ 4 , 20 , 6 , 12 ] # Function call print (longestSequence(A)) # This code is contributed by Chitranayal |
C#
// C# Program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if a // number is prime or not static bool isprime( int n) { if (n < 2) return false ; for ( int i = 2; i * i <= n; i++) if (n % i == 0) return false ; return true ; } // Function to find nearest // greater prime of given number static int nextprime( int n) { while (!isprime(n)) n++; return n; } // Function to find nearest // smaller prime of given number static int prevprime( int n) { if (n < 2) return 2; while (!isprime(n)) n--; return n; } // Function to return length of longest // possible increasing subsequence static int longestSequence( int [] A) { // Length of given array int n = A.Length; int M = 1; // Stores increasing // subsequence List< int > l = new List< int >(); // Insert first element // prevprime l.Add(prevprime(A[0])); // Traverse over the array for ( int i = 1; i < n; i++) { // Current element int x = A[i]; // Check for contribution of // nextprime and prevprime // to the increasing subsequence // calculated so far foreach ( int p in new int [] {nextprime(x), prevprime(x)}) { int low = 0; int high = M - 1; // Reset first element // of list, if p is less // or equal if (p <= l[0]) { l[0] = p; continue ; } // Finding appropriate position // of Current element in l while (low < high) { int mid = (low + high + 1) / 2; if (p > l[mid]) low = mid; else high = mid - 1; } // Update the calculated position // with Current element if (low + 1 < M) l[low + 1] = p; // Otherwise add current element // in L and increase M // as list size increases else { l.Add(p); M++; } } } // Return M as length // of possible longest // increasing sequence return M; } // Driver Code public static void Main(String[] args) { int [] A = {4, 20, 6, 12}; // Function call Console.WriteLine(longestSequence(A)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for above approach // Function to check if a // number is prime or not function isprime(n) { if (n < 2) return false ; for (let i = 2; i * i <= n; i++) if (n % i == 0) return false ; return true ; } // Function to find nearest // greater prime of given number function nextprime(n) { while (!isprime(n)) n++; return n; } // Function to find nearest // smaller prime of given number function prevprime(n) { if (n < 2) return 2; while (!isprime(n)) n--; return n; } // Function to return length of longest // possible increasing subsequence function longestSequence(A) { // Length of given array let n = A.length; let M = 1; // Stores increasing subsequence let l = new Array(); // Insert first element prevprime l.push(prevprime(A[0])); // Traverse over the array for (let i = 1; i < n; i++) { // Current element let x = A[i]; // Check for contribution of // nextprime and prevprime // to the increasing subsequence // calculated so far for (let p of [nextprime(x), prevprime(x)]) { let low = 0; let high = M - 1; // Reset first element of list, // if p is less or equal if (p <= l[0]) { l[0] = p; continue ; } // Finding appropriate position // of Current element in l while (low < high) { let mid = low + high + 1 / 2; if (p > l[mid]) low = mid; else high = mid - 1; } // Update the calculated position // with Current element if (low + 1 < M) l[low + 1] = p; // Otherwise add current element // in L and increase M // as list size increases else { l.push(p); M++; } } } // Return M as length of possible // longest increasing sequence return M; } // Driver Code let A = [ 4, 20, 6, 12 ]; // Function call document.write(longestSequence(A)); // This code is contributed by gfgking </script> |
3
Time Complexity: O(N×logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!