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 notbool 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 operationslong 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 operationsvector<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 Codeint 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 approachimport 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 notdef 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 operationsdef 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 operationsdef 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 arrayarr = [7, 3, 4, 5, 3]# Function Callprint(makePeak(arr)) |
C#
// C# program for the above approachusing 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
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!
