# Lexicographically largest N-length Bitonic sequence made up of elements from given range

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 = 6Output:5 6 5 4 3Explanation:

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 = 10Output: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)**.

- If
- 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 Code` `int` `main()` `{` ` ` `int` `N = 5, low = 2, high = 6;` ` ` `// Function Call` ` ` `LargestArray(N, low, high);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `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 Code` `public` `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 Code` `N ` `=` `5` `low ` `=` `2` `high ` `=` `6` ` ` `# Function Call` `LargestArray(N, low, high)` `# This code is contributed by code_hunt` |

## C#

`// C# program for the above approach` `using` `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 Code` `public` `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)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.