Given an array of positive integers you can reshuffle the array and construct a new array on which we can perform operation X on it the elements we receive must be in increasing in order un till the array get empty. if all the element we received are in increasing order then output is correct otherwise output is wrong
you have have to pint the array you have constructed.
operation X :we return the first element of the array and move second element at very back of the array.
Example: arr={1,2,3}
if we apply the operation x on the array once then it returns 1 to us after that we take this element pop out of the array and then pop next element form array if present and then push it back in the array at very end of array which look like {3,2} by performing operation x on it is the array
Examples :
Input : arr={1,2,3}
Output : 1 3 2
Explanation :
As if we have output array lets check we can perform all the operation
x and all the received elementals tare in the increasing order.we can
perform operation x on it 3 times.
we perform operation x first time we get 1 and the array becomes
{2,3}.
we perform the operation x second time and we get the 2 and the array
become {3}.
we can reform the operation x third time and we get the 3 and array
get empty thus we stop.
as all the elements we get are 1,2,3 are in increasing order thus the
array is the correct out put.
Input : arr={6,4,3,2,5}
Output : 2 6 3 5 4.
Explanation :
we can perform the operation x 5 times on the output array lets check
it is increasing order or not when we perform the first operation then
we receive the first element 2 and the array become {3,5,4,6}
then after 2 operation we receive 3 and array become {4,6,5}
then after 3 operation we receive 4 and array become {5,6}
then after 4 operation we receive 5 and array become {6}
then after 5 operation we receive 6 and array become empty thus we
stop as all the elements receive are 2,3,4,5,6 are increasing order
thus output is correct.
we strongly recommend to please try yourself first and then move on to the solution
Approach :
efficient
we weed to perform the operation x on the array after retrieving the element and we also need to maintain the increasing sequence so we can use the Data structure called deque that is very helpful and change over point of view toward the problem then what we can do now we can think reverse as we know that our output is increasing thus we perform the reverse process for construction of array.
Algorithm: step1: we first sort the array and iterate it from the last. step2: we pop the last element form the deque if present then push the last element of the array step3: we perform step 2 as many times uphill we traverse all elements tof the array. step4: we store the elements of the deque in the array and print the array.
#include<iostream>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;
//funtio to consruct the array
void increasing_order(int arr[],int d)
{
//using the deque
deque<int>q;
//sort the array initially
sort(arr,arr+d);
int i=0;
//constructing the array to make cards
//reveal into the increasing order
for(i=d-1;i>=0;i--)
{
if(!q.empty())
{
int k=q.back();
q.pop_back();
q.push_front(k);
}
q.push_front(arr[i]);
}
i=0;
//transfer the elements of the queue
//to the array
while(q.size()!=0)
{
arr[i]=q.front();
i=i+1;
q.pop_front();
}
}
//function to prunt the array
void print_arr(int arr[],int d)
{
int i=0;
for(i=0;i<d;i++)
{
cout<<arr[i]<<" ";
}
}
//diver funtion
int main()
{
//given a input array
int arr[]={6,4,3,2,5};
//calculation the lenght of the array
int d=sizeof(arr)/sizeof(arr[0]);
//cronstucting the array
increasing_order(arr,d);
//printing the array
print_arr(arr,d);
}
Output : 2 6 3 5 4
Time Complexity : we are iterating the array twice which is liner and sort the array once thus the Tim complexity of the above programme is O(nlog(n)). where the n is the size of the array
Space Complexity : we using the queue thus to store the element of the array thus the space complexity of the above programme is O(n). where n is the length too the array
