题解 | xgcd

"""
算法解释
1、统计奇偶个数：遍历数组，统计奇数和偶数的数量
2、特殊情况处理：
无偶数时返回 - 1
全为偶数时返回 0
3、计算操作次数：
当有至少 2 个偶数时，每个奇数只需 1 次操作变为偶数
当只有 1 个偶数时，需要 1 次额外操作生成第二个偶数，再处理剩余奇数
4、复杂度分析
时间复杂度：O (n)，其中 n 是数组长度，只需遍历数组一次
空间复杂度：O (1)，只使用了常数级别的额外空间
"""
import math

def min_operations_to_even(n, array):
    # 统计奇数和偶数的个数
    odd_count = 0
    even_count = 0
    
    for num in array:
        if num % 2 == 1:
            odd_count += 1
        else:
            even_count += 1
    
    # 如果没有偶数，无法全变为偶数
    if even_count == 0:
        return -1
    
    # 如果已经全是偶数
    if odd_count == 0:
        return 0
    
    # 如果有至少2个偶数，可以直接将奇数变为偶数
    if even_count >= 2:
        return odd_count
    
    # 如果只有1个偶数，需要先操作一次生成第二个偶数
    return odd_count

# 读取输入
n = int(input())
array = list(map(int, input().split()))

# 计算并输出结果
result = min_operations_to_even(n, array)
print(result)