Convert an array into Bitonic array by right shifting array elements
Giver an array arr[] consisting of N integers, the task is to perform right shift operations on array elements to convert the given array into a bitonic array.
Examples:
Input: arr[] = {7, 3, 4, 5, 3}
Output: 56 96 128 80 48
Explanation:
Perform the operation on the array elements as:
- 7 ? 00000111 ? 3 right shifts ? 00111000 ? 56
- 3 ? 00000011 ? 5 right shifts ? 01100000 ? 96
- 4 ? 00000100 ? 5 right shifts ? 10000000 ? 128
- 5 ? 00000101 ? 4 right shifts ? 01010000 ? 80
- 3 ? 00000011 ? 4 right shifts ? 00110000 ? 48
After the above operations the modified array is {56, 96, 128, 80, 48}, which is Bitonic array.
Input: arr[] = {255, 243, 23, 141, 46}
Output: -1
Approach: Follow the given steps to solve the problem
- Maximize the middle element of the array i.e., arr[N / 2], using right shift operations.
- Traverse the given array arr[], convert the first half of the array in ascending by performing right shift operations on the array element(if required).
- Traverse the given array arr[], convert the second half of the array in descending order via right shift operations on the array element(if required).
- After completing the above steps, check if the array is bitonic or not. Then print the array arr[] as the resultant array.
- Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; // Function to check if an // array arr[] is Bitonic or not bool isPeak(vector< long long > arr) { // Traverse the first half of arr[] for ( int i = arr.size() / 2; i < arr.size() - 1; i++) { if (arr[i] < arr[i + 1]) { return false ; } } // Traverse the second half of arr[] for ( int i = 0; i < arr.size() / 2; i++) { if (arr[i] > arr[i + 1]) { return false ; } } // Return true if arr[] is bitonic return true ; } // Function to maximize the value of N // by performing right shift operations long long maximize( long long n) { long long Ele = n; long long ans = n; for ( int idx = 0; idx < 7; idx++) { // Right shift by 1 if (Ele & 1) { Ele >>= 1; Ele += pow (2, 32); } else { Ele >>= 1; } // Update the value of ans ans = max(ans, Ele); } return ans; } // Function to arrange array in descending // order by right shift operations vector< long long > makeDec(vector< long long > arr) { // Maximise the array arr[0] long long prev = maximize(arr[0]); arr[0] = prev; // Iterate through array arr[] for ( int i = 1; i < arr.size(); i++) { long long optEle = arr[i]; // Flag to find the first // element less than prev bool flag = true ; // Update Ele as arr[i] long long Ele = arr[i]; for ( int idx = 0; idx < 7; idx++) { // Right shift by 1 if (Ele & 1) { Ele >>= 1; Ele += pow (2, 32); } else { Ele >>= 1; } if (Ele < prev && flag) { // Update the optEle optEle = Ele; // Unset the flag flag = false ; } if (Ele < prev) { // Update the optEle optEle = max(optEle, Ele); } } // Update the array arr[i] arr[i] = optEle; // Update the value of prev prev = arr[i]; } // Return the array return arr; } // Function to find the peak // element of the array arr[] vector< long long > makePeak(vector< long long > arr) { // First half of the array vector< long long > first(arr.begin(), arr.begin() + arr.size() / 2 + 1); reverse(first.begin(), first.end()); // Second half of the array vector< long long > second(arr.begin() + arr.size() / 2, arr.end()); // Merg both halves vector< long long > ans = makeDec(first); reverse(ans.begin(), ans.end()); vector< long long > secondPart = makeDec(second); secondPart.erase(secondPart.begin()); ans.insert(ans.end(), secondPart.begin(), secondPart.end()); // Function Call if (isPeak(ans)) { return ans; } vector< long long > emptyVec; return emptyVec; } // Driver Code int main() { // Given array vector< long long > arr = {7, 3, 4, 5, 3}; // Function Call vector< long long > result = makePeak(arr); if (result.size() > 0) { for ( int i = 0; i < result.size(); i++) { cout << result[i] << " " ; } } else { cout << "No peak found" ; } return 0; } // This code is contributed by Prajwal Kandekar |
Java
// Java program for the above approach import java.util.*; import java.math.*; class GFG { // Function to check if an // array arr[] is Bitonic or not static boolean isPeak(Vector <Long> arr) { // Traverse the first half of arr[] for ( int i = arr.size() / 2 ; i < arr.size() - 1 ; i++) { if (arr.get(i) < arr.get(i + 1 )) { return false ; } } // Traverse the second half of arr[] for ( int i = 0 ; i < arr.size() / 2 ; i++) { if (arr.get(i) > arr.get(i + 1 )) { return false ; } } // Return true if arr[] is bitonic return true ; } // Function to maximize the value of N // by performing right shift operations static long maximize( long n) { long Ele = n; long ans = n; for ( int idx = 0 ; idx < 7 ; idx++) { // Right shift by 1 if ((Ele & 1 ) == 1 ) { Ele >>= 1 ; Ele += Math.pow( 2 , 32 ); } else { Ele >>= 1 ; } // Update the value of ans ans = Math.max(ans, Ele); } return ans; } // Function to arrange array in descending // order by right shift operations static Vector <Long> makeDec(Vector <Long> arr) { // Maximise the array arr[0] long prev = maximize(arr.get( 0 )); arr.set( 0 , prev); // Iterate through array arr[] for ( int i = 1 ; i < arr.size(); i++) { long optEle = arr.get(i); // Flag to find the first // element less than prev boolean flag = true ; // Update Ele as arr[i] long Ele = arr.get(i); for ( int idx = 0 ; idx < 7 ; idx++) { // Right shift by 1 if ((Ele & 1 ) == 1 ) { Ele >>= 1 ; Ele += Math.pow( 2 , 32 ); } else { Ele >>= 1 ; } if (Ele < prev && flag) { // Update the optEle optEle = Ele; // Unset the flag flag = false ; } if (Ele < prev) { // Update the optEle optEle = Math.max(optEle, Ele); } } // Update the array arr[i] arr.set(i, optEle); // Update the value of prev prev = arr.get(i); } // Return the array return arr; } // Function to find the peak // element of the array arr[] static Vector <Long> makePeak(Vector <Long> arr) { // First half of the array Vector <Long> first = new Vector<Long> (arr.subList( 0 , arr.size() / 2 + 1 )); Collections.reverse(first); // Second half of the array Vector <Long> second = new Vector<Long> (arr.subList(arr.size() / 2 , arr.size())); // Merg both halves Vector <Long> ans = makeDec(first); Collections.reverse(ans); Vector <Long> secondPart = makeDec(second); secondPart.remove( 0 ); ans.addAll(secondPart); // Function Call if (isPeak(ans)) { return ans; } Vector <Long> emptyVec = new Vector<Long>(); return emptyVec; } // Driver Code public static void main(String[] args) { // Given array Vector <Long> arr = new Vector<Long> (Arrays.asList(7L, 3L, 4L, 5L, 3L)); // Function Call Vector <Long> result = makePeak(arr); if (result.size() > 0 ) { for ( int i = 0 ; i < result.size(); i++) { System.out.print(result.get(i) + " " ); } } else { System.out.print( "No peak found" ); } } } |
Python3
# Python program for the above approach # Function to check if an # array arr[] is Bitonic or not def isPeak(arr): # Traverse the first half of arr[] for i in range ( len (arr) / / 2 , len (arr) - 1 ): if arr[i] < arr[i + 1 ]: return False # Traverse the second half of arr[] for i in range ( len (arr) / / 2 ): if arr[i] > arr[i + 1 ]: return False # Return true if arr[] is bitonic return True # Function to maximize the value of N # by performing right shift operations def maximize(n): Ele = n ans = n for idx in range ( 7 ): # Right shift by 1 if Ele & 1 : Ele >> = 1 Ele + = 2 * * 32 else : Ele >> = 1 # Update the value of ans ans = max (ans, Ele) return ans # Function to arrange array in descending # order by right shift operations def makeDec(arr): # Maximise the array arr[0] prev = maximize(arr[ 0 ]) arr[ 0 ] = prev # Iterate through array arr[] for i in range ( 1 , len (arr)): optEle = arr[i] # Flag to find the first # element less than prev flag = True # Update Ele as arr[i] Ele = arr[i] for idx in range ( 7 ): # Right shift by 1 if Ele & 1 : Ele >> = 1 Ele + = 2 * * 32 else : Ele >> = 1 if Ele < prev and flag: # Update the optEle optEle = Ele # Unset the flag flag = False if Ele < prev: # Update the optEle optEle = max (optEle, Ele) # Update the array arr[i] arr[i] = optEle # Update the value of prev prev = arr[i] # Return the array return arr # Function to find the peak # element of the array arr[] def makePeak(arr): # First half of the array first = arr[: len (arr) / / 2 + 1 ] first.reverse() # Second half of the array second = arr[ len (arr) / / 2 :] # Merg both halves ans = makeDec(first)[:: - 1 ] + makeDec(second)[ 1 :] # Function Call if isPeak(ans): return ans return - 1 # Driver Code # Given array arr = [ 7 , 3 , 4 , 5 , 3 ] # Function Call print (makePeak(arr)) |
C#
// C# program for the above approach using System; using System.Collections.Generic; using System.Linq; public class Program { // Function to check if an // array arr[] is Bitonic or not static bool IsPeak(List< long > arr) { // Traverse the first half of arr[] for ( int i = arr.Count / 2; i < arr.Count - 1; i++) { if (arr[i] < arr[i + 1]) { return false ; } } // Traverse the second half of arr[] for ( int i = 0; i < arr.Count / 2; i++) { if (arr[i] > arr[i + 1]) { return false ; } } // Return true if arr[] is bitonic return true ; } // Function to maximize the value of N // by performing right shift operations static long Maximize( long n) { long ele = n; long ans = n; for ( int idx = 0; idx < 7; idx++) { // Right shift by 1 if ((ele & 1) == 1) { ele >>= 1; ele += ( long )Math.Pow(2, 32); } else { ele >>= 1; } // Update the value of ans ans = Math.Max(ans, ele); } return ans; } // Function to arrange array in descending // order by right shift operations static List< long > MakeDec(List< long > arr) { // Maximise the array arr[0] long prev = Maximize(arr[0]); arr[0] = prev; // Iterate through array arr[] for ( int i = 1; i < arr.Count; i++) { long optEle = arr[i]; // Flag to find the first // element less than prev bool flag = true ; // Update Ele as arr[i] long ele = arr[i]; for ( int idx = 0; idx < 7; idx++) { // Right shift by 1 if ((ele & 1) == 1) { ele >>= 1; ele += ( long )Math.Pow(2, 32); } else { ele >>= 1; } if (ele < prev && flag) { // Update the optEle optEle = ele; // Unset the flag flag = false ; } if (ele < prev) { // Update the optEle optEle = Math.Max(optEle, ele); } } // Update the array arr[i] arr[i] = optEle; // Update the value of prev prev = arr[i]; } // Return the array return arr; } // Function to find the peak // element of the array arr[] static List< long > MakePeak(List< long > arr) { // First half of the array List< long > first = arr.GetRange(0, arr.Count / 2 + 1); first.Reverse(); // Second half of the array List< long > second = arr.GetRange( arr.Count / 2, arr.Count - arr.Count / 2); // Merg both halves List< long > ans = MakeDec(first); ans.Reverse(); List< long > secondPart = MakeDec(second); secondPart.RemoveAt(0); ans.AddRange(secondPart); // Function Call if (IsPeak(ans)) { return ans; } return new List< long >(); } // Driver Code public static void Main() { // Given array List< long > arr = new List< long >() { 7, 3, 4, 5, 3 }; // Function Call List< long > result = MakePeak(arr); if (result.Count > 0) { Console.WriteLine( string .Join( " " , result)); } else { Console.WriteLine( "No peak found" ); } } } // This code is contributed by Prajwal Kandekar |
Output:
[1879048192, 3221225472, 4294967296, 2684354560, 1610612736]
Time Complexity: O(N * log(M)), where M is the maximum element of arr[] .
Auxiliary Space: O(N) as it is using extra space for list first and second to copy the array
Contact Us