Find Permutation of numbers in range [L, R] having X peaks and Y valleys
Given integers L, R, X and Y such that (R > L β₯ 1), (X β₯ 0) and (Y β₯ 0). Find the permutation of the numbers in range [L, R] such that there are exactly X peaks and Y valleys present in the permutation. Print Yes and the permutation if the permutation is found. Otherwise print No.
Note: In an array arr[] there is a peak at ith index if arr[i-1] < arr[i] > arr[i+1] and valley at ith index if arr[i-1] > arr[i] < arr[i+1], where 0< i < N.
Examples:
Input: L = 1, R = 3, X = 1, Y = 0
Output: Yes, arr[] = { 1, 3, 2 }
Explanation: 1 peak is required and no valley is required.
Clearly arr[0] < arr[1] > arr[2], arr[1] is the peak.Input: L = 4, R = 8, X = 4, Y = 1
Output: No
Explanation: There is no such permutation of size 5 with 4 peaks and 1 valley.Input: L = 3, R = 5, X = 0, Y = 0
Output: Yes, arr[] = { 3, 4, 5 }
Explanation: 0 peaks and 0 valleys are required.
The sorted array has no peak or valley.
Approach: There can be following five cases. Follow the approaches mentioned for each case.
Case-1(No possible permutation): The first and last element of the permutation does not contribute to the numbers of peaks and valleys.
- So if (X + Y) > (R β L β 1) there will be no permutation which satisfies the numbers of peaks and valleys.
- Also if absolute value of (X β Y) > 1, there will be no such permutation, because there is exactly 1 valley between two peaks and vice-versa.
Case-2(X = 0, Y = 0): Follow the steps mentioned below.
- Create an array arr[] of size (R β L + 1) and store the numbers in range [L, R] in sorted order in the array.
- Print the array.
Case-3(X > Y): Follow the steps mentioned below:
- Create an array arr[] of size (R β L + 1) consisting the numbers in range [L, R] in sorted order.
- Consider last (X + Y β 1) elements to assign X peaks and Y valleys.
- Iterate from i = (N β 2) to i = (N β (X + Y β 1)). where N = (R β L + 1)
- In each iteration swap arr[i] with arr[i+1] and decrement i by 2.
- Print the array
Case-4(X < Y): Follow the steps mentioned below:
- Create an array arr[] of size (R β L + 1) consisting the numbers in range [L, R] in sorted order.
- Consider first (X + Y) elements to assign X peaks and Y valleys.
- Iterate from i = 1 to i = (X+Y).
- For each iteration swap arr[i] with arr[i-1] and increment i by 2.
- Print the array.
Case-5(X = Y): Follow the steps mentioned below:
- Create an array arr[] of length (R β L + 1) consisting the numbers in range [L, R] in sorted order.
- Consider first (X+Y) elements to assign the (X-1) peaks and Y valleys.
- Iterate from i = 1 to i = (X+Y).
- For each iteration swap arr[i] with arr[i-1] and increment i by 2.
- After the iteration is complete swap the last two elements of the array to get one more peak.
- Print the array.
Given below is the implementation for the above approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Utility function to build the permutation void BuildMountainArray( int L, int R, int X, int Y) { int N = (R - L + 1); // Case-1: permutation cannot be built if (((X + Y) > (N - 2)) || abs (X - Y) > 1) { cout << "No" << endl; } else { // Vector to store the permutation vector< int > res(N, 0); for ( int index = 0; index < N; index++) { res[index] = L + index; } // Case-2: X = 0, Y = 0 if (X == 0 && Y == 0) { cout << "Yes" << endl; for ( int index = 0; index < N; index++) { cout << res[index] << " " ; } cout << endl; return ; } // Case-3: X > Y // Consider last (X+Y+1) elements else if (X > Y) { for ( int index = N - 2; index >= (N - (X + Y + 1)); index -= 2) { swap(res[index], res[index + 1]); } } // Case-4: X < Y // Consider first (X+Y) elements else if (Y > X) { for ( int index = 1; index <= (X + Y); index += 2) { swap(res[index], res[index - 1]); } } else { // Case-5: X = Y // Consider first (X+Y) elements, // it will give (X-1) peaks // and Y valleys for ( int index = 1; index <= (X + Y); index += 2) { swap(res[index], res[index - 1]); } // Swap last 2 elements, // to get 1 more peak swap(res[N - 2], res[N - 1]); } // Print the required array cout << "Yes" << endl; for ( int index = 0; index < N; index++) { cout << res[index] << " " ; } cout << endl; } } // Driver code int main() { // Input int L = 1, R = 3, X = 1, Y = 0; // Function call BuildMountainArray(L, R, X, Y); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Utility function to build the permutation static void BuildMountainArray( int L, int R, int X, int Y) { int N = (R - L + 1 ); // Case-1: permutation cannot be built if (((X + Y) > (N - 2 )) || Math.abs(X - Y) > 1 ) { System.out.println( "No" ); } else { // Vector to store the permutation int res[] = new int [N]; for ( int index = 0 ; index < N; index++) { res[index] = L + index; } // Case-2: X = 0, Y = 0 if (X == 0 && Y == 0 ) { System.out.println( "Yes" ); for ( int index = 0 ; index < N; index++) { System.out.print(res[index] + " " ); } System.out.println(); return ; } // Case-3: X > Y // Consider last (X+Y+1) elements else if (X > Y) { for ( int index = N - 2 ; index >= (N - (X + Y + 1 )); index -= 2 ) { int temp = res[index]; res[index] = res[index + 1 ]; res[index + 1 ] = temp; } } // Case-4: X < Y // Consider first (X+Y) elements else if (Y > X) { for ( int index = 1 ; index <= (X + Y); index += 2 ) { int temp = res[index]; res[index] = res[index - 1 ]; res[index - 1 ] = temp; } } else { // Case-5: X = Y // Consider first (X+Y) elements, // it will give (X-1) peaks // and Y valleys for ( int index = 1 ; index <= (X + Y); index += 2 ) { int temp = res[index]; res[index] = res[index - 1 ]; res[index - 1 ] = temp; } // Swap last 2 elements, // to get 1 more peak int temp = res[N - 2 ]; res[N - 2 ] = res[N - 1 ]; res[N - 1 ] = temp; } // Print the required array System.out.println( "Yes" ); for ( int index = 0 ; index < N; index++) { System.out.print(res[index] + " " ); } System.out.println(); } } // Driver code public static void main(String[] args) { // Input int L = 1 , R = 3 , X = 1 , Y = 0 ; // Function call BuildMountainArray(L, R, X, Y); } } // This code is contributed by Potta Lokesh |
Python3
# Python code to implement the above approach import math as Math # Utility function to build the permutation def BuildMountainArray(L, R, X, Y): N = (R - L + 1 ) # Case-1: permutation cannot be built if (((X + Y) > (N - 2 )) or Math.fabs(X - Y) > 1 ): print ( "No" ) else : # Vector to store the permutation res = [ 0 ] * N for index in range (N): res[index] = L + index # Case-2: X = 0, Y = 0 if (X = = 0 and Y = = 0 ): print ( "Yes" ) for index in range (N): print (res[index], end = " " ) print ("") return # Case-3: X > Y # Consider last (X+Y+1) elements elif (X > Y): for index in range (N - 2 , N - (X + Y + 1 ) - 1 , - 2 ): temp = res[index] res[index] = res[index + 1 ] res[index + 1 ] = temp # Case-4: X < Y # Consider first (X+Y) elements elif (Y > X): for index in range ( 1 , X + Y + 1 , 2 ): temp = res[index] res[index] = res[index - 1 ] res[index - 1 ] = temp else : # Case-5: X = Y # Consider first (X+Y) elements, # it will give (X-1) peaks # and Y valleys for index in range ( 1 , X + Y + 1 , 2 ): temp = res[index] res[index] = res[index - 1 ] res[index - 1 ] = temp # Swap last 2 elements, # to get 1 more peak temp = res[N - 2 ] res[N - 2 ] = res[N - 1 ] res[N - 1 ] = temp # Print the required array print ( "Yes" ) for index in range (N): print (res[index], end = " " ) print ("") # Driver code # Input L = 1 R = 3 X = 1 Y = 0 # Function call BuildMountainArray(L, R, X, Y) # This code is contributed by Saurabh jaiswal |
C#
// C# implementation of above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Utility function to build the permutation static void BuildMountainArray( int L, int R, int X, int Y) { int N = (R - L + 1); // Case-1: permutation cannot be built if (((X + Y) > (N - 2)) || Math.Abs(X - Y) > 1) { Console.WriteLine( "No" ); } else { // Vector to store the permutation int [] res = new int [N]; for ( int index = 0; index < N; index++) { res[index] = L + index; } // Case-2: X = 0, Y = 0 if (X == 0 && Y == 0) { Console.WriteLine( "Yes" ); for ( int index = 0; index < N; index++) { Console.Write(res[index] + " " ); } Console.WriteLine(); return ; } // Case-3: X > Y // Consider last (X+Y+1) elements else if (X > Y) { for ( int index = N - 2; index >= (N - (X + Y + 1)); index -= 2) { int temp1 = res[index]; res[index] = res[index + 1]; res[index + 1] = temp1; } } // Case-4: X < Y // Consider first (X+Y) elements else if (Y > X) { for ( int index = 1; index <= (X + Y); index += 2) { int temp2 = res[index]; res[index] = res[index - 1]; res[index - 1] = temp2; } } else { // Case-5: X = Y // Consider first (X+Y) elements, // it will give (X-1) peaks // and Y valleys for ( int index = 1; index <= (X + Y); index += 2) { int temp3 = res[index]; res[index] = res[index - 1]; res[index - 1] = temp3; } // Swap last 2 elements, // to get 1 more peak int temp4 = res[N - 2]; res[N - 2] = res[N - 1]; res[N - 1] = temp4; } // Print the required array Console.WriteLine( "Yes" ); for ( int index = 0; index < N; index++) { Console.Write(res[index] + " " ); } Console.WriteLine(); } } // Driver Code public static void Main() { // Input int L = 1, R = 3, X = 1, Y = 0; // Function call BuildMountainArray(L, R, X, Y); } } // This code is contributed sanjoy_62. |
Javascript
<script> // JavaScript code to implement the above approach // Utility function to build the permutation const BuildMountainArray = (L, R, X, Y) => { let N = (R - L + 1); // Case-1: permutation cannot be built if (((X + Y) > (N - 2)) || Math.abs(X - Y) > 1) { document.write( "No<br/>" ); } else { // Vector to store the permutation let res = new Array(N).fill(0); for (let index = 0; index < N; index++) { res[index] = L + index; } // Case-2: X = 0, Y = 0 if (X == 0 && Y == 0) { document.write( "Yes<br/>" ); for (let index = 0; index < N; index++) { document.write(`${res[index]} `); } document.write( "<br/>" ); return ; } // Case-3: X > Y // Consider last (X+Y+1) elements else if (X > Y) { for (let index = N - 2; index >= (N - (X + Y + 1)); index -= 2) { let temp = res[index]; res[index] = res[index + 1]; res[index + 1] = temp; } } // Case-4: X < Y // Consider first (X+Y) elements else if (Y > X) { for (let index = 1; index <= (X + Y); index += 2) { let temp = res[index]; res[index] = res[index - 1]; res[index - 1] = temp; } } else { // Case-5: X = Y // Consider first (X+Y) elements, // it will give (X-1) peaks // and Y valleys for (let index = 1; index <= (X + Y); index += 2) { let temp = res[index]; res[index] = res[index - 1]; res[index - 1] = temp; } // Swap last 2 elements, // to get 1 more peak let temp = res[N - 2]; res[N - 2] = res[N - 1]; res[N - 1] = temp; } // Print the required array document.write( "Yes<br/>" ); for (let index = 0; index < N; index++) { document.write(`${res[index]} `); } document.write( "<br/>" ); } } // Driver code // Input let L = 1, R = 3, X = 1, Y = 0; // Function call BuildMountainArray(L, R, X, Y); // This code is contributed by rakeshsahni </script> |
Yes 1 3 2
Time Complexity: O(N) where N = (R β L + 1)
Space Complexity: O(N)