Beat The Odds (Codeforces 1691A)
Tags: Greedy, brute force

Given a sequence $$$a_1, a_2, \ldots, a_n$$$, find the minimum number of elements to remove from the sequence such that after the removal, the sum of every $$$2$$$ consecutive elements is even.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\dots,a_n$$$ ($$$1\leq a_i\leq10^9$$$) — elements of the sequence.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every $$$2$$$ consecutive elements is even.

Note: In the first test case, after removing $$$3$$$, the sequence becomes $$$[2,4,6,8]$$$. The pairs of consecutive elements are $$$\{[2, 4], [4, 6], [6, 8]\}$$$. Each consecutive pair has an even sum now. Hence, we only need to remove $$$1$$$ element to satisfy the condition asked.In the second test case, each consecutive pair already has an even sum so we need not remove any element.

Sample Inputs:
2
5
2 4 3 6 8
6
3 5 9 7 1 3

Sample Outputs:
1
0

Solution (Python):
for s in [*open(0)][2::2]:
    a = [0, 0]
    for x in s.split():
        a[int(x) % 2] += 1
    print(min(a))

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

def solve(n, a):
    (o, e) = (0, 0)
    for i in a:
        if i % 2 == 0:
            e += 1
        else:
            o += 1
    return min(o, e)
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    res2 = solve(n, a)
    print(res2)

Solution (Python):
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    odd = sum((1 for x in arr if x % 2 != 0))
    even = n - odd
    print(min(odd, even))

def main():
    T = int(input())
    for _ in range(T):
        solve()
if __name__ == '__main__':
    main()