Moving Chips (Codeforces 1923A)
Tags: Greedy, implementation

There is a ribbon divided into $$$n$$$ cells, numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell either contains a chip or is free.You can perform the following operation any number of times (possibly zero): choose a chip and move it to the closest free cell to the left. You can choose any chip that you want, provided that there is at least one free cell to the left of it. When you move the chip, the cell where it was before the operation becomes free.Your goal is to move the chips in such a way that they form a single block, without any free cells between them. What is the minimum number of operations you have to perform?

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.Each test case consists of two lines:  the first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of cells;  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$); $$$a_i = 0$$$ means that the $$$i$$$-th cell is free; $$$a_i = 1$$$ means that the $$$i$$$-th cell contains a chip. Additional constraint on the input: in each test case, at least one cell contains a chip.

Output: For each test case, print one integer — the minimum number of operations you have to perform so that all chips form a single block without any free cells between them.

Note: In the first example, you can perform the operation on the chip in the $$$7$$$-th cell. The closest free cell to the left is the $$$5$$$-th cell, so it moves there. After that, all chips form a single block.In the second example, all chips are already in a single block. Same for the third example.

Sample Inputs:
5
8
0 1 1 1 0 1 1 0
6
0 1 0 0 0 0
6
1 1 1 1 1 1
5
1 0 1 0 1
9
0 1 1 0 0 0 1 1 0

Sample Outputs:
1
0
0
2
3

Solution (Python):
t = int(input())
A = []
for i in range(t):
    l = int(input())
    s = input().split(' ')
    for j in range(l):
        s[j] = int(s[j])
    for j in range(l):
        if s[j] == 1:
            break
        s[j] = 1
    for j in range(l - 1, -1, -1):
        if s[j] == 1:
            break
        s[j] = 1
    A.append(s.count(0))
for i in A:
    print(i)

Solution (Python):
t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    (l, r) = (a.index(1), n - a[::-1].index(1) - 1)
    c = a.count(1)
    print(r - l - c + 1)

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
    n = int(input())
    s = input()
    s = s.strip()
    s = s.strip(' 0')
    c = 0
    for i in s:
        if i == '0':
            c += 1
    print(c)