1777A - Everybody Likes Good Arrays! - 800

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()