CODEM3 - Problem3
Arrays are one of the most basic and widely used data structures. While data structures like stack, queues, linked list etc are often considered as advanced, so we will be playing with arrays only at the moment. So let us play a simple game. We play the game as follows: You will be given an array of integers and you can swap any two elements of the given array at a time. Swapping cost is 1 unit. The aim of the game is to append all zeros if present in the array to the end while keeping order of its element.
Find the minimum cost to obtain the aim of the game.
Input
First line contains a number T. (number of test cases)
For each test case 2 lines follow,
First line contains size of array, n <= 10^6.
Second line contains the array elements. (-10^9 <= value of elements <= 10^9)
Output
For each test case print on separate line the minimum cost to obtain the aim.
Example
Input: 3
4
1 3 0 2
4
1 2 3 0
4
1 2 3 5 Output: 1
0
0
Explanation
For first case swap 0 and 2, so the array becomes 1 3 2 0. Hence all zeros at the end and order of elements is preserved. (i.e. 1 was before 3, 3 was after 1 and before 2 and so on. )
hide comments
ankitmaurya_19:
2021-05-20 06:18:06
Consider this test case
|
|
lx_lovin:
2019-08-09 05:29:44
very easy O(1) in average case and O(logn) in worst case
|
|
anupam125:
2019-05-15 14:34:39
1
|
|
anupam125:
2019-05-15 14:28:24
not getting testcases why my solution is wrong.
|
|
chunky_2808:
2018-10-04 17:23:50
@suvro_coder output will be 2 as order of element matters
|
|
devyash17:
2018-06-13 19:31:29
Last edit: 2018-06-13 19:36:37 |
|
suvro_coder:
2018-06-13 18:42:09
@raj its output will be 1!
|
|
coderanant:
2018-05-23 13:15:46
@raj its output is 2 Last edit: 2018-05-23 19:05:56 |
|
raj:
2017-12-07 22:12:22
what should be the output of the following testcase ?
|
|
lovedeep_9697:
2017-08-13 20:49:06
please provide us with the testcases |
Added by: | Bhavik |
Date: | 2014-02-04 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem(for CODE MARATHON) |