Close

Up down array

Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]
For example consider the array A =[6, 9, 36, 24, 42]
The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We have to find out one such answer.
We can solve this problem in a simpler way by sorting the array first. Considering the same example as above
Sorted(A) = [6, 9, 24, 36, 42]
Method1: Start from the second element and swap the elements in pairs
6, 9<-> 24, 36<-> 42 ===>  6, 24, 9, 42, 36
Method2: Interleave the elements of the second half into the first half in reverse order
It becomes 6, 42, 9, 36, 24

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int t;
cin >> t;
while( t-- )
{
int n,i;
cin >> n;
vector<int> nums(n);
for( i = 0; i < n; i++ )
{
cin >> nums[i];
}
sort(nums.begin(), nums.end());
for( i = 1; i < n-1; i += 2)
{
swap(nums[i], nums[i+1]);
}
for( i = 0; i < n; i++ )
cout << nums[i] << " ";
cout << endl;
}
return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *