xgcd

[题目链接](https://www.nowcoder.com/practice/397173cff1744ed88512b573c71ef3ba)

思路

给定长度为 $n$ 的数组 $a$ ，每次操作可以选定两个下标 $i, j$ ，将 $a_i$ 和 $a_j$ 同时变换。目标是用最少操作使所有元素变为偶数，若不可能则输出 $-1$ 。

奇偶性分析

核心观察：操作只在奇偶性层面产生影响。

考虑数组中奇数元素和偶数元素的关系：

若所有元素都是偶数：无需操作，答案为 $0$ 。

若所有元素都是奇数：无论如何操作，都无法将全部元素变为偶数。答案为 $-1$ 。

若既有奇数又有偶数：每个奇数元素可以通过与某个偶数元素配合，在一次操作中变为偶数。因此每个奇数需要恰好一次操作，答案为奇数元素的个数。

为什么全为奇数时无解？

当数组中所有元素均为奇数时，任何一次操作都涉及两个奇数元素。由于奇数之间的变换不会产生偶数（无法借助偶数元素"中转"），因此始终无法全部变为偶数。

为什么有偶数时答案恰好等于奇数个数？

当存在偶数元素时，每次操作可以利用一个偶数元素将一个奇数元素变为偶数，且不会破坏已有偶数元素的偶数性质。因此每个奇数元素恰好需要一次操作，总操作数等于奇数元素个数。

样例演示

$a = [1, 2]$ ： $1$ 个奇数，存在偶数，答案为 $1$ 。
$a = [1, 1]$ ： $2$ 个奇数，全为奇数，答案为 $-1$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int odd = 0;
    for(int i = 0; i < n; i++){
        int x;
        scanf("%d", &x);
        if(x % 2 == 1) odd++;
    }
    if(odd == 0){
        printf("0\n");
    } else if(odd == n){
        printf("-1\n");
    } else {
        printf("%d\n", odd);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int odd = 0;
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (x % 2 == 1) odd++;
        }
        if (odd == 0) {
            System.out.println(0);
        } else if (odd == n) {
            System.out.println(-1);
        } else {
            System.out.println(odd);
        }
    }
}

复杂度分析

时间复杂度： $O(n)$ 。遍历一次数组统计奇数个数。
空间复杂度： $O(1)$ 。仅使用常数额外空间。