To solve this problem, we need to determine the maximum number of non-overlapping pairs of integers such that the sum of each pair is even.
Approach
The sum of two integers is even if and only if both integers are either even or odd. This leads us to the following observations:
- Even + Even = Even
- Odd + Odd = Even
- Even + Odd = Odd (not valid for our problem)
Thus, the maximum number of valid pairs is the sum of:
- The number of pairs we can form from even numbers (each pair uses two even numbers).
- The number of pairs we can form from odd numbers (each pair uses two odd numbers).
Solution Code
n = int(input())
nums = list(map(int, input().split()))
even = 0
odd = 0
for num in nums:
if num % 2 == 0:
even += 1
else:
odd += 1
print((even // 2) + (odd // 2))
Explanation
- Input Reading: We first read the number of integers and the list of integers.
- Count Even and Odd: We iterate through the list and count how many even and odd numbers there are.
- Calculate Pairs: For even numbers, the number of pairs is the integer division of the count of even numbers by 2. Similarly, for odd numbers, it's the integer division of the count of odd numbers by 2. Adding these two values gives the maximum number of valid pairs.
This approach efficiently computes the result in linear time, O(n), where n is the number of integers, making it optimal for the problem constraints. The space complexity is O(1) (excluding input storage) since we only use a few variables to count even and odd numbers.
Answer: The code will output the maximum number of non-overlapping pairs with even sum. For example, if the input is 5 followed by 1 2 3 4 5, the output is 2. If the input is 4 followed by 1 3 5 7, the output is 2. If the input is 3 followed by 2 4 6, the output is 1.
The final answer depends on the input values, but the code correctly computes it as described. For the given problem (assuming standard input), the code will provide the correct result.
The answer is the value obtained from the code as explained.


作者声明:本文包含人工智能生成内容。