All Tracks Algorithms Sorting Merge Sort Problem

Median Game

Algorithms, June Easy 19, Logic-Based, Merge sort, Sorting


You are given an array \(A\) of \(N\) integers. You perform this operation \(N - 2\) times: For each contiguous subarray of odd size greater than \(2\), you find the median of each subarray(Say medians obtained in a move are \(M_1, M_2, M_3,\ldots, M_k\)). In each move, you remove the first occurrence of value \(min(M_1, M_2, M_3,\ldots, M_k)\) from the original array. After removing the element the array size reduces by 1 and no void spaces are left. For example, if we remove element \(2\) from the array \(\{1, 2, 3, 4\}\), the new array will be \(\{1, 3, 4\}\).

Print a single integer denoting the sum of numbers that are left in the array after performing the operations. You need to do this for \(T\) test cases.

Input Format

The first line contains \(T\) denoting the number of test cases(\(1 \le T \le 10\)). 

The first line of each test case contains \(N\) denoting the number of integers in the array initially(\(4 \le N \le 10^5\)).

The next line contains \(N\) space seperated integers denoting \(A_1, A_2, A_3,\ldots, A_N\)(\(1 \le A_i \le 10^9\) for all valid \(i\)).

Output Format

Output a single integer denoting the sum of numbers left in the array after performing the operations for each test case on a new line.

2 5 3 2
1 1 1 1

For the first test case:  Initially, array is \(\{2, 5, 3, 2\}\). The medians obtained are \(\{3, 3\}\) for subarrays \([1, 3]\) and \([2, 4]\) respectively. Hence, we remove \(min(3, 3) = 3\) from the initial array. The array now becomes \(\{2, 5, 2\}\). The median of the whole array is \(2\). Hence we remove the first occurrence of \(2\) from the array. So, we are left with \(\{5, 2\}\) in our array.

 For the second test case, it is obvious that the minimum medium will be \(1\) every time. Hence finally, we will be left with \(\{1, 1\}\) as the array.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications