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 Codeint 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 approachimport 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 approachfrom 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 Codeif __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 approachusing 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 Codepublic 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 Codevar N = 5, L = 3, R = 10;// Function CallbitonicSequence(N, L, R);</script> |
Output:
[9, 10, 9, 8, 7]
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!
