Maximize length of increasing subsequence possible by replacing array element by nearest primes
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 notbool 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 numberint nextprime(int n){ while (!isprime(n)) n++; return n;}// Function to find nearest// smaller prime of given numberint prevprime(int n){ if (n < 2) return 2; while (!isprime(n)) n--; return n;}// Function to return length of longest// possible increasing subsequenceint 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 Codeint 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 approachimport 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 notdef 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 numberdef nextprime(n): while (not isprime(n)): n += 1 return n# Function to find nearest# smaller prime of given numberdef prevprime(n): if (n < 2): return 2 while (not isprime(n)): n -= 1 return n# Function to return length of longest# possible increasing subsequencedef 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 Codeif __name__ == "__main__": A = [4, 20, 6, 12] # Function call print(longestSequence(A))# This code is contributed by Chitranayal |
C#
// C# Program for // the above approachusing System;using System.Collections.Generic;class GFG{// Function to check if a// number is prime or notstatic 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 numberstatic int nextprime(int n){ while (!isprime(n)) n++; return n;}// Function to find nearest// smaller prime of given numberstatic int prevprime(int n){ if (n < 2) return 2; while (!isprime(n)) n--; return n;}// Function to return length of longest// possible increasing subsequencestatic 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 Codepublic 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 notfunction 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 numberfunction nextprime(n){ while (!isprime(n)) n++; return n;}// Function to find nearest// smaller prime of given numberfunction prevprime(n){ if (n < 2) return 2; while (!isprime(n)) n--; return n;}// Function to return length of longest// possible increasing subsequencefunction 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 Codelet A = [ 4, 20, 6, 12 ];// Function calldocument.write(longestSequence(A));// This code is contributed by gfgking</script> |
Output:
3
Time Complexity: O(N×logN)
Auxiliary Space: O(N)
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!
