Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 3 Jun, 2021

Easy

```
Given ‘N’ = 4,
'ARR' = { 4, 3, 2, 1}
Then a possible array is 3, 4, 1, 2.
```

```
You are supposed to return the array, which is in a zig-zag fashion.
Since there can be multiple answers for a particular array, any of the possible solutions are accepted.
It can be proved. A zig-zag array is always possible for a given array.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array.
The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.
```

```
For each test case, You are supposed to return a zig-zag array for the given array. The runner function will print a single line containing a single integer which denotes whether the returned array is in zig-zag fashion or not.
```

```
You are not required to print the expected output; it has already been taken care of. Just implement the function.
```

```
1 <= ‘T’ <= 10
1 <= ‘N’ <= 5*10^3
0 <= 'ARR'[i] <= 10 ^ 6
Time Limit: 1sec.
```

The idea is to sort the array and swap the pair of elements starting from index 1 (0-based Indexing).

The steps are as follows:

- Sort the array in ascending order.
- Loop ‘i’ = 0, from index 1 to ‘N’ and at each iteration increase ‘i’ by 2.
- Swap elements at positions ‘i’ and ‘i + 1’.

- We will return the array ‘arr’ as the final answer.

The idea is to use a modified one pass of bubble sort. This means swapping elements if they are not in position.

The steps are as follows:

- Traverse the array, from 0th position to ‘N’-2 th position.
- Maintain a bool variable ‘flag’ for representing which order currently we need, greater than or less than.
- If the current two elements, i.e., the element at ‘i’ and ‘i’+1th position, are not in that order, then swap those elements; otherwise, not.

- We will return ‘arr’ as the final answer.