Last Updated: 14 Jun, 2021
Ninja And Alternating Largest
Easy
Asked in company
Ninja is given a few numbers, and he is being asked to rearrange the numbers so that every second element is greater than its left and right element.
Suppose the given array is [1, 2, 3, 4, 5] then the rearranged array can be [1, 3, 2, 5, 4].
Input Format:
The first line of input contains a single integer T, representing the number of test cases.
The first line of each test case contains ‘N’, denoting the number of elements in the array.
The second line of each test case contains the array elements.
Output Format :
The first and only line of each test case in the output contains 1 if the array satisfies the conditions mentioned.
Note:
If the array returned is the rearranged array following all the conditions, then it will print 1 else it will print 0.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
0 <= array[i] <= 10^5
Time limit: 1 sec
Approaches
We will sort the array. Then we take an auxiliary array and fill it with the elements of the sorted array starting from both the ends in an alternate order.
The steps are as follows:
- We sort the array.
- We take two pointers ‘l’ to mark the first element of the array, ‘r’ to mark the last element of the array, and ‘k’ to mark the present element of an array.
- We run a while loop as long as l < r.
- We store in an auxiliary array A[k] the value of array[i] and increment both i and k.
- We store in an auxiliary array A[k] the value of array[j] and increment k and decrement j simultaneously.
- Finally, we return the array ‘A’ as the final answer.
We will traverse the array and check if every second element is greater than the left and right elements. If the present element is less than its left element, then we swap the elements. If the current element is less than its right element, then we swap the elements. We continue this for every alternate element. Finally, we return the rearranged array as our final answer.
The steps are as follows:
- We run a for loop and traverse every alternate element starting from 1, i.e., i = 1 to i = N-1:
- If the value of array[i] is less than the element at index i - 1, we swap the elements.
- If the value of array[i] is less than the element at index i + 1 and i + 1 is less than N, we swap the elements.
- Finally, we return the array as the final answer.