Subsequence of Size K With the Largest Even Sum

Subsequence of Size K With the Largest Even Sum

What is this problem about?

In this problem, you are given an array of integers and an integer k. You need to find a subsequence of length k such that the sum of its elements is as large as possible AND the sum is an even number. If no such subsequence exists, you should return -1. A subsequence is formed by deleting zero or more elements from the original array while keeping the relative order of the remaining elements.

Why is this asked in interviews?

Companies like Microsoft ask this question to test a candidate's ability to combine sorting with greedy logic. It is more complex than simply picking the k largest elements because those might sum to an odd number. It requires the candidate to identify the "minimal adjustments" needed to turn an odd sum into an even one by swapping elements between odd and even groups. It tests logical reasoning and edge-case handling.

Algorithmic pattern used

This problem uses a Greedy Approach with Sorting.

1. Sort the array in descending order and take the sum of the first k elements.
2. If the sum is already even, you are done.
3. If the sum is odd, you have two options to make it even:
   • Replace the smallest even number in the sum with the largest odd number outside the sum.
   • Replace the smallest odd number in the sum with the largest even number outside the sum.
4. You check both options and pick the one that results in the larger even sum.

Example explanation (use your own example)

Array: [4, 1, 5, 3, 2], k = 3.

1. Sorted: [5, 4, 3, 2, 1].
2. Top 3: [5, 4, 3]. Sum = 12.
3. 12 is already even. Result: 12. Wait, let's try k=2:
4. Top 2: [5, 4]. Sum = 9 (Odd).
5. Smallest even in sum: 4. Largest odd outside: 3. Swap: [5, 3], sum = 8.
6. Smallest odd in sum: 5. Largest even outside: 2. Swap: [4, 2], sum = 6. Max even sum is 8.

Common mistakes candidates make

The most common mistake is not considering both swap options (replacing an even with an odd or an odd with an even). Only checking one of these can lead to a sub-optimal or incorrect result. Another mistake is not handling the case where there are no even or odd numbers available for a swap, which would make the swap impossible. Candidates also sometimes forget that the result must be even and might incorrectly return a larger odd sum.

Interview preparation tip

When solving the Subsequence of Size K With the Largest Even Sum interview question, start by picking the k largest numbers greedily. Then, discuss how to fix the parity. This "Greedy then Adjust" strategy is very effective for parity-based problems. Be sure to mention the O(n log n) time complexity due to sorting.