Generate Bitonic Sequence of length N from integers in a given range
Given integers N, L and R, the task is to generate a Bitonic Sequence of length N from the integers in the range [L, R] such that the first element is the maximum. If it is not possible to create such a sequence, then print “-1”.
A Bitonic Sequence is a sequence that must be strictly increasing at first and then strictly decreasing.
Examples:
Input: N = 5, L = 3, R = 10
Output: 9, 10, 9, 8, 7
Explanation: The sequence {9, 10, 9, 8, 7} is first strictly increasing and then strictly decreasing.Input: N = 5, L = 2, R = 5
Output: 4, 5, 4, 3, 2
Explanation:
[ The sequence {4, 5, 4, 3, 2} is first strictly increasing and then strictly decreasing.
Approach: The idea is to use a Deque so that elements can be added from the end and the beginning. Follow the steps below to solve the problem:
- Initialize a deque to store the element of the resultant bitonic sequence.
- Initialize a variable i as 0 and start adding elements in the resultant list starting from (R – i) until i less than the minimum of (R – L + 1) and (N – 1).
- After the above steps if the size of the resultant list is less than N then add elements from (R – 1) to L from the starting of the list until the size of the resultant list does not become N.
- After the above steps, if N is greater than (R – L)*2 + 1, then it is not possible to construct such a sequence then print “-1” else print the sequence stored in deque.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to construct bitonic // sequence of length N from // integers in the range [L, R] void bitonicSequence( int num, int lower, int upper) { // If sequence is not possible if (num > (upper - lower) * 2 + 1) { cout << -1; return ; } // Store the resultant list deque< int > ans; deque< int >::iterator j = ans.begin(); for ( int i = 0; i < min(upper - lower + 1, num - 1); i++) ans.push_back(upper - i); // If size of deque < n for ( int i = 0; i < num - ans.size(); i++) // Add elements from start ans.push_front(upper - i - 1); // Print the stored in the list cout << '[' ; for (j = ans.begin(); j != ans.end(); ++j) cout << ' ' << *j; cout << ' ' << ']' ; } // Driver Code int main() { int N = 5, L = 3, R = 10; // Function Call bitonicSequence(N, L, R); return 0; } // This code is contributed by jana_sayantan |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to construct bitonic // sequence of length N from // integers in the range [L, R] public static void bitonicSequence( int num, int lower, int upper) { // If sequence is not possible if (num > (upper - lower) * 2 + 1 ) { System.out.println(- 1 ); return ; } // Store the resultant list Deque<Integer> ans = new ArrayDeque<>(); for ( int i = 0 ; i < Math.min(upper - lower + 1 , num - 1 ); i++) ans.add(upper - i); // If size of deque < n for ( int i = 0 ; i < num - ans.size(); i++) // Add elements from start ans.addFirst(upper - i - 1 ); // Print the stored in the list System.out.println(ans); } // Driver Code public static void main(String[] args) { int N = 5 , L = 3 , R = 10 ; // Function Call bitonicSequence(N, L, R); } } |
Python3
# Python3 program for the above approach from collections import deque # Function to construct bitonic # sequence of length N from # integers in the range [L, R] def bitonicSequence(num, lower, upper): # If sequence is not possible if (num > (upper - lower) * 2 + 1 ): print ( - 1 ) return # Store the resultant list ans = deque() for i in range ( min (upper - lower + 1 , num - 1 )): ans.append(upper - i) # If size of deque < n for i in range (num - len (ans)): # Add elements from start ans.appendleft(upper - i - 1 ) # Print the stored in the list print ( list (ans)) # Driver Code if __name__ = = '__main__' : N = 5 L = 3 R = 10 # Function Call bitonicSequence(N, L, R) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to construct bitonic // sequence of length N from // integers in the range [L, R] public static void bitonicSequence( int num, int lower, int upper) { // If sequence is not possible if (num > (upper - lower) * 2 + 1) { Console.WriteLine(-1); return ; } // Store the resultant list List< int > ans = new List< int >(); for ( int i = 0; i < Math.Min(upper - lower + 1, num - 1); i++) ans.Add(upper - i); // If size of deque < n for ( int i = 0; i < num - ans.Count; i++) // Add elements from start ans.Insert(0,upper - i - 1); // Print the stored in the list Console.Write( "[" ); foreach ( int x in ans) Console.Write(x + ", " ); Console.Write( "]" ); } // Driver Code public static void Main(String[] args) { int N = 5, L = 3, R = 10; // Function Call bitonicSequence(N, L, R); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for the above approach // Function to construct bitonic // sequence of length N from // integers in the range [L, R] function bitonicSequence(num, lower, upper) { // If sequence is not possible if (num > (upper - lower) * 2 + 1) { document.write( -1); return ; } // Store the resultant list var ans = []; for ( var i = 0; i < Math.min(upper - lower + 1, num - 1); i++) ans.push(upper - i); // If size of deque < n for ( var i = 0; i < num - ans.length; i++) { // Add elements from start ans.splice(0, 0, upper -i - 1) } // Print the stored in the list document.write( '[' ); ans.forEach(element => { document.write( " " +element); }); document.write( ' ' + ']' ); } // Driver Code var N = 5, L = 3, R = 10; // Function Call bitonicSequence(N, L, R); </script> |
[9, 10, 9, 8, 7]
Time Complexity: O(N)
Auxiliary Space: O(1)