求解数组全为偶数的最少操作次数及代码错误排查

操作奇偶性规律 #

首先我们只需要关注元素的奇偶性即可求解，选择下标i执行操作时，两个元素的奇偶性变化规则如下：

• 若A[i]和A[i+1]均为奇数：操作后二者都变为偶数，操作次数+1，奇数总数量减2
• 若A[i]和A[i+1]一奇一偶：操作后二者都变为奇数，操作次数+1，奇数总数量加1
• 若二者均为偶数：操作无变化，无意义

测试用例1 #

输入：N=6，arr = [1,6,4,3,4,2]，预期输出4，具体步骤：

1. 操作i=0：数组变为[7, -5, 4, 3, 4, 2]，操作次数1
2. 操作i=1：数组变为[7, -1, -9, 3, 4, 2]，操作次数2
3. 操作i=2：数组变为[7, -1, -6, -12, 4, 2]，操作次数3
4. 操作i=0：数组变为[6, 8, -6, -12, 4, 2]，全为偶数，总操作次数4

测试用例2 #

输入：N=6，arr = [1,6,4,3,5,2]，预期输出3，具体步骤：

1. 操作i=3：数组变为[1, 6, 4, 8, -2, 2]，操作次数1
2. 操作i=0：数组变为[7, -5, 4, 8, -2, 2]，操作次数2
3. 操作i=0：数组变为[2, 12, 4, 8, -2, 2]，全为偶数，总操作次数3

你的代码逻辑存在两个核心问题：

1. 没有考虑奇数总数为奇数的场景，此时最后会剩余单个奇数，需要额外操作将其转换为两个相邻奇数再消除
2. 两个奇数的操作次数不等于下标差：当两个奇数距离为d且d为奇数时，操作次数为d+1而非d，比如测试用例1中两个奇数距离为3，实际需要4次操作

该问题可以用位运算高效求解：
因为我们只需要判断元素奇偶性，用x & 1即可快速得到奇偶性（结果为1是奇数，0是偶数），比取模运算性能更高。
正确参考实现如下：

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    res = 0
    i = 0
    while i < n:
        if (arr[i] & 1) == 0:
            i += 1
            continue
        res += 1
        if i + 1 >= n:
            break
        # 操作后下一个元素必然为奇数，直接标记后移动指针
        arr[i+1] |= 1
        i += 1
    print(res)

内容的提问来源于stack exchange，提问作者justjokingbro