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.


-----Examples-----

Input
2
5
2 4 3 6 8
6
3 5 9 7 1 3
Output
1
0


-----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.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Mathematics

Greedy algorithms


Solutions:
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	o = 0
	e = 0
	for i in l:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if o > e:
		print(e)
	else:
		print(o)


T = int(input())
while T:
	N = int(input())
	li = list(map(int, input().split()))
	c = 0
	for ele in li:
		if ele % 2:
			c += 1
	print(min(c, N - c))
	T -= 1


def solve():
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ec = 0
	oc = 0
	for ele in arr:
		if ele % 2 == 0:
			ec += 1
		else:
			oc += 1
	print(min(ec, oc))
t = int(input())
for i in range(t):
	solve()


import sys

def main():
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 6)
	t = int(input())
	for _ in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		pair = len([x for x in l if x % 2 == 1])
		print(min(pair, len(l) - pair))
main()


def solve(n, arr):
	c = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			c += 1
	return min(c, n - c)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for x in a:
		if x % 2 == 1:
			cnt += 1
	if cnt > n - cnt:
		print(n - cnt)
	else:
		print(cnt)


def minNums(numbers):
	even = 0
	odd = 0
	for num in numbers:
		if num % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd < even:
		return odd
	else:
		return even
t = int(input())
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	print(minNums(numbers))


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	uneven_count = sum((e % 2 for e in a))
	even_count = len(a) - uneven_count
	ans.append(min(uneven_count, even_count))
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for x in arr:
		if x % 2 == 0:
			ans += 1
	print(min(ans, n - ans))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if a[i] & 1:
			ans += 1
	ans = min(ans, n - ans)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().rstrip().split()))
	count = 0
	for i in l:
		if i & 1:
			count += 1
	if n > 2 * count:
		print(count)
	else:
		print(n - count)
	t -= 1


def min_seq(n, l):
	e = 0
	o = 0
	for i in l:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	return e if o > e else o
tc = int(input())
for i in range(tc):
	n = int(input())
	l = list(map(int, input().split()))
	ANS = min_seq(n, l)
	print(ANS)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	(e, o) = (0, 0)
	for i in a:
		if i & 1:
			o += 1
		else:
			e += 1
	m = min(e, o)
	print(m)


n = int(input())
for i in range(n):
	t = input()
	s = list(map(int, input().split()))
	so = len(list(filter(lambda x: x % 2 == 1, s)))
	se = len(s) - so
	print(min(se, so))


def min_elimination(n, arr):
	countOdd = 0
	for i in range(n):
		if arr[i] % 2:
			countOdd += 1
	return min(countOdd, n - countOdd)
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = min_elimination(n, arr)
	print(res)


for i in range(int(input())):
	length = int(input())
	array = input().split()
	even = sum((1 - int(n) % 2 for n in array))
	odd = len(array) - even
	print(even if even <= odd else odd)


t = int(input())
for x in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	o = 0
	e = 0
	for x in l:
		if x % 2:
			o += 1
		else:
			e += 1
	print(min(e, o))


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	odd = even = 0
	for i in b:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	print(min(odd, even))


def isEven(n):
	return n % 2 == 0

def Solve(N, A):
	cnt = 0
	for i in range(N):
		if A[i] & 1:
			cnt += 1
	return min(N - (N - cnt), N - cnt)
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(Solve(N, A))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	o = len(list(filter(lambda x: x % 2 != 0, l)))
	e = len(l) - o
	if o > e:
		print(e)
	else:
		print(o)


for i in range(int(input())):
	n = int(input())
	a = sum((int(i) % 2 for i in input().split()))
	b = n - a
	print(min(a, b))


i = int(input())
for x in range(i):
	k = int(input())
	l = [int(y) % 2 for y in input().split()]
	m = l.count(0)
	n = l.count(1)
	if m > n:
		print(n)
	else:
		print(m)


def count(arr):
	e = 0
	o = 0
	for i in arr:
		if int(i) % 2 == 0:
			e += 1
		else:
			o += 1
	return min(e, o)
n = int(input())
for i in range(n):
	a = int(input())
	x = input()
	x = x.split(' ')
	print(count(x))


import sys

def get_string():
	return sys.stdin.readline().strip()

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_num():
	return int(sys.stdin.readline().strip())

def solve():
	n = get_num()
	arr = get_list()
	odd = len([i for i in arr if i & 1 == 1])
	even = n - odd
	print(min(even, odd))
cases = int(input())
for i in range(cases):
	solve()


for f in range(int(input())):
	f = input()
	array = map(int, input().split())
	even = 0
	odd = 0
	for a in array:
		if a % 2 == 0:
			even += 1
		else:
			odd += 1
	print(min(even, odd))


for _ in [0] * int(input()):
	n = int(input())
	a = [*map(int, input().split())]
	b = len([i for i in a if i % 2])
	print(min(b, n - b))


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	lista_impares = [i for i in a if i % 2 == 1]
	impares = len(lista_impares)
	pares = len(a) - impares
	print(pares) if pares < impares else print(impares)


I = lambda : map(int, input().split())
(t,) = I()
for i in range(t):
	(n,) = I()
	l = I()
	e = sum([1 if x % 2 == 0 else 0 for x in l])
	print(min(e, n - e))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = even = 0
	for num in a:
		if num & 1:
			odd += 1
		else:
			even += 1
	print(min(odd, even))


m = int(input())
for i in range(m):
	n = int(input())
	m = list(map(int, input().split()))
	z = [int(0.0), int(0.0)]
	for i in m:
		z[i % 2] += 1
	print(min(z))


def main():
	input_number_test_case = input()
	number_test_cases = int(input_number_test_case)
	for index in range(number_test_cases):
		number_items = int(input())
		items = input()
		pairs = [item for item in items.split(' ') if int(item) % 2 == 0]
		print(number_items - len(pairs) if int(number_items / 2) < len(pairs) else len(pairs))
main()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	A = list(map(lambda x: int(x) % 2, input().strip().split(' ')))
	print(min(A.count(1), A.count(0)))


def solve():
	cc = 0
	x = int(input())
	l = list(map(int, input().split()))
	for i in l:
		if i % 2:
			cc += 1
	return min(cc, x - cc)
res = []
n = int(input())
for i in range(n):
	r = solve()
	res.append(r)
for i in res:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	a_list = list(map(int, input().split()))
	odds = len([a for a in a_list if a % 2 == 1])
	evens = len([a for a in a_list if a % 2 == 0])
	print(min(odds, evens))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	ceven = 0
	codd = 0
	for i in a:
		if i & 1 == 1:
			codd += 1
		else:
			ceven += 1
	print(min(codd, ceven))
	t -= 1


def beatOdds():
	t = int(input())
	for i in range(t):
		n = int(input())
		l1 = list(map(int, input().split()))
		even = 0
		odd = 0
		for j in l1:
			if j % 2 == 0:
				even += 1
			else:
				odd += 1
		if even == n or odd == n:
			print(0)
		else:
			print(min(even, odd))
beatOdds()


num_test_cases = input()
for _ in range(int(num_test_cases)):
	_ = input()
	nums = input()
	nums = nums.split(' ')
	nums = [int(i) % 2 for i in nums]
	odd = sum(nums)
	if odd > len(nums) // 2:
		print(len(nums) - odd)
	else:
		print(odd)


for _ in range(int(input())):
	a = int(input())
	li = tuple(map(int, input().split()))
	dem = 0
	if li[0] % 2:
		for i in li[1:]:
			if i % 2 == 0:
				dem += 1
	else:
		for i in li[1:]:
			if i % 2:
				dem += 1
	if dem > len(li) - dem:
		print(len(li) - dem)
	else:
		print(dem)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i & 1 == 1:
			c += 1
	print(min(c, n - c))


tests = int(input())
for t in range(tests):
	n = int(input())
	nums = list(map(int, input().split()))
	odds = sum([1 for elem in nums if elem % 2 == 1])
	print(min(n - odds, odds))


t = int(input())
for i in range(t):
	l = int(input())
	c = 0
	lst = list(map(int, input().split()))
	for i in lst:
		if i % 2 != 0:
			c += 1
	if l == c:
		print(0)
	else:
		print(min(c, l - c))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(odd, even) = (0, 0)
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	print(min(odd, even))


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	ec = 0
	oc = 0
	for i in l:
		if i % 2 == 0:
			ec += 1
		else:
			oc += 1
	if ec == 0 or oc == 0:
		print(0)
	elif ec > oc:
		print(oc)
	else:
		print(ec)
	t = t - 1


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
for i in range(n):
	elem = inp()
	l = list(invr())
	odd = 0
	even = 0
	for x in l:
		if x % 2 == 0:
			even += 1
		else:
			odd += 1
	print(min(even, odd))


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	cnt1 = 0
	cnt2 = 0
	for i in a:
		if i % 2 == 0:
			cnt1 += 1
		else:
			cnt2 += 1
	if cnt1 >= cnt2:
		print(cnt2)
	else:
		print(cnt1)


def process(arr, n):
	res = 0
	for i in range(n):
		if arr[i] & 1:
			res += 1
	res = min(res, n - res)
	return res
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	print(process(arr, n))


from sys import stdin
for i in range(int(stdin.readline())):
	k = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	cnt = [0, 0]
	for a in arr:
		cnt[a & 1] += 1
	print(min(cnt))


for _ in range(int(input())):
	n = int(input())
	odds = 0
	evens = 0
	for a in map(int, input().split()):
		if a % 2 == 0:
			evens += 1
		else:
			odds += 1
	print(min(odds, evens))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	e = 0
	for i in range(n):
		if lst[i] % 2 == 0:
			e += 1
	o = n - e
	print(min(e, o))


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(n):
		if a[j] % 2 == 0:
			count = count + 1
	print(min(count, n - count))


def nene(a):
	k1 = 0
	k2 = 0
	for i in a:
		if i % 2 == 0:
			k2 += 1
		else:
			k1 += 1
	return [k1, k2]
n = int(input())
for i in range(n):
	t = int(input())
	a = [int(x) for x in input().split()]
	print(min(nene(a)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		if i % 2 == 0:
			c += 1
	x = n - c
	print(min(c, x))


t = int(input())
for i in range(t):
	n = int(input())
	list1 = [int(x) for x in input().split()]
	(count_of_even, count_of_odd) = (0, 0)
	for i in range(n):
		if list1[i] % 2 != 0:
			count_of_odd += 1
	print(min(count_of_odd, n - count_of_odd))


t = int(input())
for i in range(t):
	a = int(input())
	s = list(map(int, input().split()))
	(g, h) = (0, 0)
	for i in s:
		if i & 1 == 0:
			g += 1
		else:
			h += 1
	print(min(g, h))


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	(evens, odds) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			evens += 1
	odds = n - evens
	print(min(evens, odds))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	oddCount = 0
	evenCount = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			evenCount += 1
		else:
			oddCount += 1
	if oddCount > evenCount:
		print(evenCount)
	else:
		print(oddCount)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(lambda x: int(x) % 2 == 0, input().split(' ')))
	es = sum(a)
	print(min(n - es, es))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		c += i % 2
	print(min(c, n - c))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	sum1 = 0
	sum2 = 0
	for j in range(n):
		if a[j] % 2 == 0:
			sum2 += 1
		else:
			sum1 += 1
	if sum1 > sum2:
		print(sum2)
	else:
		print(sum1)


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	count = 0
	for i in L:
		if i % 2 == 0:
			count += 1
	print(min(count, n - count))


from sys import stdin

def solution(arr):
	(odd, even) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd < even:
		print(odd)
	else:
		print(even)
for _ in range(int(input())):
	(size, arr) = (int(input()), list(map(int, input().split())))
	solution(arr)


import sys
sys.setrecursionlimit(int(1000000000.0))
input = sys.stdin.readline
print = lambda *x, sep=' ', end='\n': sys.stdout.write(sep.join(map(str, x)) + end)
t = int(input())
for case in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	evens = 0
	odds = 0
	for num in nums:
		if num % 2 == 0:
			evens += 1
		else:
			odds += 1
	print(min(evens, odds))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	count_o = 0
	count_e = 0
	for i in range(n):
		if l[i] % 2 == 1:
			count_o += 1
	count_e = n - count_o
	print(min(count_e, count_o))


for _ in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	odd_c = even_c = even = odd = 0
	for i in t:
		if i % 2 == 0:
			even_c += 1
		elif i % 2 == 1:
			odd_c += 1
	print(min(even_c, odd_c))


n = int(input())
total = []
for g in range(n):
	total.append([0, 0])
	nofn = int(input())
	num = list(map(int, input().strip().split()))
	for i in num:
		if i % 2 == 0:
			total[-1][0] += 1
		else:
			total[-1][1] += 1
for i in range(len(total)):
	print(min(total[i]))


from sys import stdin

def minimum_num(elements):
	even = 0
	uneven = 0
	for num in elements:
		if num % 2 == 0:
			even = even + 1
		else:
			uneven = uneven + 1
	if even > uneven:
		return uneven
	else:
		return even

def main():
	t_cases = int(stdin.readline().strip())
	for t in range(t_cases):
		n_numbers = stdin.readline().strip()
		elements = [int(x) for x in stdin.readline().strip().split()]
		answer = minimum_num(elements)
		print(answer)
main()


noft = int(input(''))
for l in range(0, noft):
	ln = int(input(''))
	ctr = 0
	for j in input().split(' '):
		if int(j) % 2 == 0:
			ctr += 1
	print(min(ctr, ln - ctr))


t = int(input())
l = []
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l.append(l1)
for j in l:
	l2 = []
	for k in j:
		if k % 2 == 0:
			l2.append(k)
	if len(l2) <= len(j) // 2:
		print(len(l2))
	else:
		print(len(j) - len(l2))


t = int(input())
ans = []
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd = 0
	even = 0
	for x in a:
		if x % 2 == 0:
			even += 1
		else:
			odd += 1
	ans.append(min(even, odd))
for a in ans:
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	lt = list(map(int, input().split()))
	(o, c) = (0, 0)
	for j in lt:
		if j % 2 == 1:
			o += 1
		else:
			c += 1
	print(min(o, c))


N = int(input())
for n in range(N):
	k = int(input())
	seq = list(map(int, input().split()))
	count = 0
	for num in seq:
		if num % 2 == 0:
			count += 1
	print(min(count, k - count))


t = int(input())

def solve():
	n = int(input())
	lst = [int(x) for x in input().split()]
	ct = 0
	for x in lst:
		if x % 2 == 0:
			ct += 1
	if ct < n / 2:
		print(ct)
	else:
		print(n - ct)
for x in range(t):
	solve()


def solution(n, nums):
	(odd, eve) = (0, 0)
	for k in nums:
		if k % 2 == 0:
			eve += 1
		else:
			odd += 1
	print(min(odd, eve))
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	solution(n, nums)


for _ in range(int(input())):
	n = int(input())
	f = sum((x % 2 == 0 for x in list(map(int, input().split()))))
	print(min(f, n - f))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	even = odd = 0
	res = 0
	for num in a:
		if num % 2 == 0:
			even += 1
		else:
			odd += 1
	print(even if odd >= even else odd)


def CNT(arr):
	ev = 0
	od = 0
	for i in arr:
		if i % 2 == 0:
			ev += 1
		else:
			od += 1
	return (ev, od)
for i in range(int(input())):
	l = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	print(min(CNT(arr)))


def r(i):
	return int(i) % 2
for i in range(int(input())):
	a = input()
	a = list(map(r, input().split()))
	print(min(a.count(0), a.count(1)))


no = int(input())
for i in range(no):
	n = int(input())
	list1 = list(map(int, input().split()))
	oddCount = 0
	evenCount = 0
	for i in list1:
		if i % 2 == 1:
			oddCount += 1
		else:
			evenCount += 1
	print(min(oddCount, evenCount))


n = int(input(''))

def s_1(lst):
	n_f = 0
	n_z = 0
	for i in lst:
		if int(i) % 2 == 0:
			n_z += 1
		else:
			n_f += 1
	if n_z <= n_f:
		print(n_z)
	else:
		print(n_f)
for i in range(n):
	input('')
	lst = input('').split(' ')
	s_1(lst)


def main():
	input_number_test_case = input()
	number_test_cases = int(input_number_test_case)
	test_cases = []
	for index in range(number_test_cases):
		number_items = input()
		items = input()
		test_cases.append({'number_items': int(number_items), 'items': [int(item) for item in items.split(' ')]})
	get_results(test_cases)

def get_results(test_cases):
	for test_case in test_cases:
		odd = []
		pair = []
		for item in test_case['items']:
			if item % 2 == 0:
				pair.append(item)
			else:
				odd.append(item)
		print(len(odd) if len(odd) < len(pair) else len(pair))
main()


n = int(input())
data = [list(map(int, input().split())) for a in range(n * 2)]
num = [data[b] for b in range(1, len(data), 2)]
for c in num:
	(odd, even) = (0, 0)
	for d in c:
		if d % 2 == 0:
			even += 1
		else:
			odd += 1
	print(min([odd, even]))


caseT = int(input())
for i in range(caseT):
	T = int(input())
	lstT = list(map(int, input().split()))
	countO = 0
	for i in lstT:
		if i % 2 == 0:
			countO += 1
	ans = min(T - countO, countO)
	print(ans)


t = int(input())
for te in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(e, o) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	print(min(e, o))


t = int(input())
for i in range(t):
	n = int(input())
	list = input().split(' ')
	(odd, even) = (0, 0)
	for f in list:
		if int(f) % 2 == 0:
			odd += 1
		else:
			even += 1
	if odd > even:
		print(even)
	else:
		print(odd)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	ce = 0
	co = 0
	for i in A:
		if i % 2 == 0:
			ce += 1
		else:
			co += 1
	m = min(ce, co)
	print(m)


T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(0, len(arr)):
		if arr[i] % 2 != 0:
			count += 1
	n = len(arr) - count
	if n > count:
		print(count)
	elif n < count:
		print(n)
	else:
		print(n)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if a[i] % 2 == 0:
			count += 1
	m = n - count
	if m > count:
		print(count)
	elif count > m:
		print(m)
	else:
		print(m)
	t = t - 1