Given three integers N, low and high, the task is to find the lexicographically largest bitonic sequence consisting of N elements lying in the range [low, high]. If it is not possible to generate such a sequence, then print “Not Possible”.
Examples:
Input: N = 5, low = 2, high = 6
Output: 5 6 5 4 3
Explanation:
The sequence {arr[0], arr[1]} is strictly increasing followed by strictly decreasing sequence of the remaining elements. This sequence is the lexicographically largest possible having all elements in the range [2, 6] and length of this sequence is 5.Input: N = 10, low = 4, high = 10
Output: 7 8 9 10 9 8 7 6 5 4
Approach: The idea is to find the suitable index of high in the resultant sequence and then maintain a difference of 1 between adjacent elements in the sequence such that the bitonic sequence formed is the lexicographically largest possible. Follow the steps below to solve the problem:
- Initialize an array A[] of size N to store the resultant sequence.
- Initialize a variable high_index = -1 to store the index of high in A[] and set high_index = N – (high – low + 1).
- If high_index > (N – 1) / 2, then the remaining N/2 elements cannot be placed in strictly increasing order. So, print “Not Possible”.
- Otherwise, perform the following steps:
- If high_index ? 0, then set high_index = 1 as there has to be a strictly increasing sequence at the beginning.
- Maintain a strictly decreasing sequence with a difference of 1 from the range [high_index, 0], starting with a value high.
- Maintain a strictly decreasing sequence with a difference of 1 from the range[high_index + 1, N – 1] starting with a value (high – 1).
- After completing the above steps, print all the elements in array A[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the lexicographically// largest bitonic sequence of size N// elements lies in the range[low, high]void LargestArray(int N, int low, int high){ // Store index of highest element int high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { cout << "Not Possible"; return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence int A[N]; // Store the high value int temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for (int i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for (int i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for (int i = 0; i < N; i++) { cout << A[i] << ' '; }}// Driver Codeint main(){ int N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG{ // Function to find the lexicographically// largest bitonic sequence of size N// elements lies in the range[low, high]static void LargestArray(int N, int low, int high){ // Store index of highest element int high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { System.out.print("Not Possible"); return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence int[] A = new int[N]; // Store the high value int temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for(int i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for(int i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for(int i = 0; i < N; i++) { System.out.print(A[i] + " "); }} // Driver Codepublic static void main(String[] args){ int N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high);}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach # Function to find the lexicographically# largest bitonic sequence of size N# elements lies in the range[low, high]def LargestArray(N, low, high): # Store index of highest element high_index = N - (high - low + 1) # If high_index > (N-1)/2, then # remaining N/2 elements cannot # be placed in bitonic order if (high_index > (N - 1) // 2): print("Not Possible") return # If high_index <= 0, then # set high_index as 1 if (high_index <= 0): high_index = 1 # Stores the resultant sequence A = [0] * N # Store the high value temp = high # Maintain strictly decreasing # sequence from index high_index # to 0 starting with temp for i in range(high_index, -1, -1): # Store the value and decrement # the temp variable by 1 A[i] = temp temp = temp - 1 # Maintain the strictly decreasing # sequence from index high_index + 1 # to N - 1 starting with high - 1 high -= 1 for i in range(high_index + 1, N): # Store the value and decrement # high by 1 A[i] = high high = high - 1 # Print the resultant sequence for i in range(N): print(A[i], end = " ")# Driver CodeN = 5low = 2high = 6 # Function CallLargestArray(N, low, high)# This code is contributed by code_hunt |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the lexicographically// largest bitonic sequence of size N// elements lies in the range[low, high]static void LargestArray(int N, int low, int high){ // Store index of highest element int high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { Console.Write("Not Possible"); return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence int[] A = new int[N]; // Store the high value int temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for(int i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for(int i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for(int i = 0; i < N; i++) { Console.Write(A[i] + " "); }}// Driver Codepublic static void Main(String[] args){ int N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// Javascript program for the above approach// Function to find the lexicographically// largest bitonic sequence of size N// elements lies in the range[low, high]function LargestArray(N, low, high){ // Store index of highest element let high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { document.write("Not Possible"); return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence let A = []; // Store the high value let temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for(let i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for(let i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for(let i = 0; i < N; i++) { document.write(A[i] + " "); }}// Driver Code let N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high); </script> |
Output:
5 6 5 4 3
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
