Queries on insertion of an element in a Bitonic Sequence
Given a Bitonic sequence ‘S’ and ‘Q’ no. of queries. Each query contain an integer xi, 1 <= i <= Q. The task is to print the length of bitonic sequence after inserting the integer for each query. Also, print the bitonic sequence after all the queries.
Examples:
Input: S = { 1, 2, 5, 2 }, Q = 4, x = { 5, 1, 3, 2 }
Output:
4
5
6
6
Bitonic Sequence: 1 2 3 5 2 1Explanation:
- For the 1st query, we need to insert x1 = 5 but since 5 is the maximum element and we can have only one occurrence of the maximum element in S, so we won’t insert 5 in S. Hence, size = 4.
- For the 2nd query, we need to insert x2 = 1, so we insert it in decreasing part as increasing part already has 1 in it. Hence, size = 5.
- For 3rd query, we insert x3 = 3 in increasing side so size becomes 6.
- For 4th query, we cannot insert x2 = 2 since 2 is in both increasing and decreasing side.
Input: S = { 1, 2, 5, 2 }, Q = 4, x = { 5, 6, 4, 4 }
Output:
4
5
6
7
Bitonic Sequence: 1 2 4 5 6 4 2
Approach: The idea is to make two sets, one for increasing sequence and other for decreasing sequence.
- Now, for each query, first check if the xi is greater than the maximum element in the bitonic sequence or not.
- If yes, update the maximum sequence and include that element in the set for increasing sequence.
- If no, then check if that element is present in the increasing sequence set, if not include it in increasing sequence set, else include it into decreasing sequence set.
Below is the implementation of this approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the bitonic sequence void solveQuery( int a[], int n, int x[], int q) { int maxx = INT_MIN; // Finding the maximum element for ( int i = 0; i < n; i++) maxx = max(maxx, a[i]); set< int > s1, s2; s1.insert(a[0]); s2.insert(a[n - 1]); // set to include increasing sequence element for ( int i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.insert(a[i]); // set to include decreasing sequence element for ( int i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.insert(a[i]); // removing maximum element from // decreasing sequence set s2.erase(s2.find(maxx)); // for each query for ( int i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.insert(x[i]); } else { // checking if x lie in increasing sequence if (s1.find(x[i]) == s1.end()) s1.insert(x[i]); // else insert into decreasing sequence set else s2.insert(x[i]); } // finding the length int ans = s1.size() + s2.size(); cout << ans << "\n" ; } // printing the sequence set< int >::iterator it; for (it = s1.begin(); it != s1.end(); it++) cout << (*it) << " " ; set< int >::reverse_iterator rit; for (rit = s2.rbegin(); rit != s2.rend(); rit++) cout << (*rit) << " " ; } // Driver code int main() { int a[] = { 1, 2, 5, 2 }; int n = sizeof (a) / sizeof (a[0]); int x[] = { 5, 1, 3, 2 }; int q = sizeof (x) / sizeof (x[0]); solveQuery(a, n, x, q); return 0; } |
Java
// Java implementation of above approach import java.util.*; class GFG { // Function to find the bitonic sequence static void solveQuery( int a[], int n, int x[], int q) { int maxx = Integer.MIN_VALUE; // Finding the maximum element for ( int i = 0 ; i < n; i++) maxx = Math.max(maxx, a[i]); Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>(); s1.add(a[ 0 ]); s2.add(a[n - 1 ]); // set to include increasing sequence element for ( int i = 1 ; i < n; i++) if (a[i] > a[i - 1 ]) s1.add(a[i]); // set to include decreasing sequence element for ( int i = n - 2 ; i >= 0 ; i--) if (a[i] > a[i + 1 ]) s2.add(a[i]); // removing maximum element from // decreasing sequence set s2.remove(maxx); // for each query for ( int i = 0 ; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.add(x[i]); } else { // checking if x lie in increasing sequence if (!s1.contains(x[i])) s1.add(x[i]); // else insert into decreasing sequence set else s2.add(x[i]); } // finding the length int ans = s1.size() + s2.size(); System.out.print(ans + "\n" ); } // printing the sequence for (Integer it : s1) System.out.print((it) + " " ); for (Integer it : s2) System.out.print((it) + " " ); } // Driver code public static void main(String[] args) { int a[] = { 1 , 2 , 5 , 2 }; int n = a.length; int x[] = { 5 , 1 , 3 , 2 }; int q = x.length; solveQuery(a, n, x, q); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of above approach import sys # Function to find the bitonic sequence def solveQuery(a, n, x, q): maxx = - sys.maxsize # Finding the maximum element for i in range (n): maxx = max (maxx, a[i]) s1, s2 = set (), set () s1.add(a[ 0 ]) s2.add(a[n - 1 ]) # set to include increasing sequence element for i in range ( 1 , n): if a[i] > a[i - 1 ]: s1.add(a[i]) # set to include decreasing sequence element for i in range (n - 2 , - 1 , - 1 ): if a[i] > a[i + 1 ]: s2.add(a[i]) # removing maximum element from # decreasing sequence set s2.remove(maxx) # for each query for i in range (q): # checking if x is greater than # maximum element or not. if maxx < = x[i]: maxx = x[i] s1.add(x[i]) else : # checking if x lie in increasing sequence if x[i] not in s1: s1.add(x[i]) # else insert into decreasing sequence set else : s2.add(x[i]) # finding the length ans = len (s1) + len (s2) print (ans) # printing the sequence for i in s1: print (i, end = " " ) for i in reversed ( list (s2)): print (i, end = " " ) # Driver Code if __name__ = = "__main__" : a = [ 1 , 2 , 5 , 2 ] n = len (a) x = [ 5 , 1 , 3 , 2 ] q = len (x) solveQuery(a, n, x, q) # This code is contributed by # sanjeev2552 |
C#
// C# implementation of above approach using System; using System.Collections.Generic; class GFG { // Function to find the bitonic sequence static void solveQuery( int []a, int n, int []x, int q) { int maxx = int .MinValue; // Finding the maximum element for ( int i = 0; i < n; i++) maxx = Math.Max(maxx, a[i]); HashSet< int > s1 = new HashSet< int >(), s2 = new HashSet< int >(); s1.Add(a[0]); s2.Add(a[n - 1]); // set to include increasing sequence element for ( int i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.Add(a[i]); // set to include decreasing sequence element for ( int i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.Add(a[i]); // removing maximum element from // decreasing sequence set s2.Remove(maxx); // for each query for ( int i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.Add(x[i]); } else { // checking if x lie in increasing sequence if (!s1.Contains(x[i])) s1.Add(x[i]); // else insert into decreasing sequence set else s2.Add(x[i]); } // finding the length int ans = s1.Count + s2.Count; Console.Write(ans + "\n" ); } // printing the sequence foreach ( int it in s1) Console.Write((it) + " " ); foreach ( int it in s2) Console.Write((it) + " " ); } // Driver code public static void Main(String[] args) { int []a = { 1, 2, 5, 2 }; int n = a.Length; int []x = { 5, 1, 3, 2 }; int q = x.Length; solveQuery(a, n, x, q); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of above approach // Function to find the bitonic sequence function solveQuery(a, n, x, q) { let maxx = Number.MIN_VALUE; // Finding the maximum element for (let i = 0; i < n; i++) maxx = Math.max(maxx, a[i]); let s1 = new Set(); let s2 = new Set(); s1.add(a[0]); s2.add(a[n - 1]); // set to include increasing sequence element for (let i = 1; i < n; i++) if (a[i] > a[i - 1]) s1.add(a[i]); // set to include decreasing sequence element for (let i = n - 2; i >= 0; i--) if (a[i] > a[i + 1]) s2.add(a[i]); // removing maximum element from // decreasing sequence set s2. delete (maxx); // for each query for (let i = 0; i < q; i++) { // checking if x is greater than // maximum element or not. if (maxx <= x[i]) { maxx = x[i]; s1.add(x[i]); } else { // checking if x lie in increasing sequence if (!s1.has(x[i])) s1.add(x[i]); // else insert into decreasing sequence set else s2.add(x[i]); } // finding the length let ans = s1.size + s2.size; document.write(ans + "</br>" ); } let S1 = Array.from(s1); S1.sort( function (a, b){ return a - b}); // printing the sequence S1.forEach ( function (it) { document.write(it + " " ); }) s2.forEach ( function (it) { document.write(it + " " ); }) } let a = [ 1, 2, 5, 2 ]; let n = a.length; let x = [ 5, 1, 3, 2 ]; let q = x.length; solveQuery(a, n, x, q); // This code is contributed by decode2207. </script> |
Output
4 5 6 6 1 2 3 5 2 1
Contact Us