 # 1777A - Everybody Likes Good Arrays! - 800

Updated: 2023-09-01

1777A - Everybody Likes Good Arrays! (greedy, math, 800)

## Statement

• You have an array of numbers, and you want to make it “good.” A good array is one where every pair of adjacent numbers has different parity (one is even, and the other is odd).
• You can do this by performing operations on pairs of adjacent numbers with the same parity (both even or both odd), and replacing them with their product.

## Logic

1. Loop through the array
2. Check the parity of the current element and the previous element
3. If the parity is the same, perform the operation and increment the operation counter
4. Repeat steps 2 and 3 until the end of the array
5. Return the operation counter

## Solution

def solve(n, ar):
res = 0
i = 0
while i < len(ar) - 1:
if ar[i] % 2 == ar[i + 1] % 2:
ar[i] = ar[i] * ar[i + 1]
del ar[i + 1]
res += 1
else:
i += 1
return res


## Optimized Solution

1. Check how many times the parity changes in the given array.
2. The number of operations needed is the difference between the original length of the array and the count of parity changes.
def solve():
n = int(input())
ar = list(map(int, input().split()))

# Count the number of times the parity changes in the array
last_parity = None
parity_count = 0
for x in ar:
if x % 2 != last_parity:
parity_count += 1
last_parity = x % 2

# The result is the difference between the original length and the count of parity changes
res = n - parity_count
print(res)

for _ in range(int(input())):
solve()