Jobs

Interviews

Discussions

Subsequence of Size K With the Largest Even Sum

Medium

Asked by:

34 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums and an integer k.

Return the largest even sum of a subsequence of nums that has size k. If there is no such subsequence, return -1.

A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,1,5,3,2], k = 3
Output: 12
Explanation:
The subsequence with the largest even sum is [4,3,5] which has a sum of 12.

Example 2:

Input: nums = [4,6,2], k = 3
Output: 12
Explanation:
The subsequence with the largest even sum is [4,6,2] which has a sum of 12.

Example 3:

Input: nums = [1,3,5], k = 1
Output: -1
Explanation:
There is no subsequence of size 1 that has an even sum.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵
1 <= k <= nums.length

Try coding it in LeetCode

Subsequence of Size K With the Largest Even Sum

Medium

Asked by:

34 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums and an integer k.

Return the largest even sum of a subsequence of nums that has size k. If there is no such subsequence, return -1.

A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,1,5,3,2], k = 3
Output: 12
Explanation:
The subsequence with the largest even sum is [4,3,5] which has a sum of 12.

Example 2:

Input: nums = [4,6,2], k = 3
Output: 12
Explanation:
The subsequence with the largest even sum is [4,6,2] which has a sum of 12.

Example 3:

Input: nums = [1,3,5], k = 1
Output: -1
Explanation:
There is no subsequence of size 1 that has an even sum.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵
1 <= k <= nums.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the integer `k`?
Can the elements in `nums` be negative, zero, or only positive integers?
What should be returned if no subsequence of size `k` with an even sum can be formed? Is it always -1, or can it be something else?
Does the order of elements in the input array `nums` matter, or can we assume it's unsorted?
If there are multiple subsequences of size `k` that yield the largest possible even sum, does it matter which one we choose, or should we return a specific one based on some criteria (e.g., lexicographically smallest)?

Brute Force Solution

Approach

This problem asks us to find a way to pick a specific number of items from a larger collection so that the sum of the chosen items is even and as large as possible. The brute force method involves trying out every single possible combination of items we could pick.

Here's how the algorithm would work step-by-step:

First, consider every single way to pick the required number of items from the collection.
For each group of items you've picked, calculate their total sum.
Check if that total sum is an even number.
If the sum is even, compare it to the largest even sum you've found so far.
If the current sum is larger than the best one you've seen, remember it as the new largest even sum.
After you have looked at all possible combinations of items, the largest even sum you've recorded is your answer.

Code Implementation

import itertoolsdef find_largest_even_subsequence_sum(numbers, subsequence_size):    largest_even_sum_found = -1    all_combinations = itertools.combinations(numbers, subsequence_size)    # We need to iterate through every possible group of numbers to check their sums.    for current_combination in all_combinations:        current_sum = sum(current_combination)        # Ensure the sum is even before considering it as a potential largest even sum.        if current_sum % 2 == 0:            # If the current even sum is greater than what we've seen, update our record.            if current_sum > largest_even_sum_found:                largest_even_sum_found = current_sum    # If no even sum was found, it remains -1. Otherwise, it holds the largest one.    return largest_even_sum_found

Big(O) Analysis

Time Complexity

O(nCk * k) – The problem requires checking every possible subsequence of size k. The number of ways to choose k items from a set of n items is given by the binomial coefficient 'n choose k' (nCk). For each of these nCk subsequences, we then iterate through the k elements to calculate their sum. Therefore, the total number of operations is approximately nCk multiplied by k, leading to a time complexity of O(nCk * k).

Space Complexity

O(1) – The brute force approach described involves iterating through combinations. For each combination, we calculate a sum and potentially store the largest even sum found so far. These operations only require a few variables (e.g., to hold the current sum and the maximum even sum), which do not depend on the input size N. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The best way to find the largest even sum subsequence of a specific size is to first consider the largest possible numbers. We then strategically swap out numbers to ensure the sum is even while keeping it as large as possible.

Here's how the algorithm would work step-by-step:

Separate all the numbers into two groups: one for even numbers and one for odd numbers.
Initially, pick the largest numbers from both groups to form a preliminary subsequence. Aim to fill the required size with the biggest numbers available.
Calculate the sum of this preliminary subsequence. If the sum is already even, and we used the largest possible numbers to reach the required size, we are done.
If the sum is odd, we need to make a change. To change an odd sum to an even sum, we must change an odd number of odd numbers in our subsequence. The simplest way to do this with minimal impact on the sum is to swap one odd number with one even number.
Consider swapping the smallest odd number we included with the largest odd number we left out. Or, consider swapping the smallest even number we included with the largest even number we left out.
Choose the swap that results in the largest possible sum that is now even. If no such swap is possible that maintains the required subsequence size, it means we cannot achieve an even sum for that size with the given numbers.
If we can make a valid swap, update the subsequence and its sum. If the sum is still odd after considering all the best swaps, repeat the swapping process, trying to make the smallest possible reduction in the sum to achieve an even result.
If at any point we cannot form a subsequence of the required size, or if we exhaust all possibilities to make the sum even, then a solution doesn't exist.

Code Implementation

def largest_even_sum_subsequence(input_numbers, subsequence_size):
    even_numbers = sorted([num for num in input_numbers if num % 2 == 0], reverse=True)
    odd_numbers = sorted([num for num in input_numbers if num % 2 != 0], reverse=True)

    current_subsequence = []
    current_sum = 0

    # Greedily pick largest numbers first to maximize sum
    even_index = 0
    odd_index = 0

    while len(current_subsequence) < subsequence_size:
        if even_index < len(even_numbers) and odd_index < len(odd_numbers):
            if even_numbers[even_index] > odd_numbers[odd_index]:
                current_subsequence.append(even_numbers[even_index])
                current_sum += even_numbers[even_index]
                even_index += 1
            else:
                current_subsequence.append(odd_numbers[odd_index])
                current_sum += odd_numbers[odd_index]
                odd_index += 1
        elif even_index < len(even_numbers):
            current_subsequence.append(even_numbers[even_index])
            current_sum += even_numbers[even_index]
            even_index += 1
        elif odd_index < len(odd_numbers):
            current_subsequence.append(odd_numbers[odd_index])
            current_sum += odd_numbers[odd_index]
            odd_index += 1
        else:
            # Not enough numbers to form the subsequence
            return -1

    # If the initial sum is even, we found the optimal subsequence
    if current_sum % 2 == 0:
        return current_sum

    # If the sum is odd, we need to make swaps to make it even
    # The goal is to minimize the reduction in sum while achieving an even sum.

    min_sum_reduction = float('inf')
    best_even_sum = -1

    # Try swapping smallest odd in subsequence with largest even out of subsequence
    smallest_odd_in = float('inf')
    index_smallest_odd_in = -1
    for i, num in enumerate(current_subsequence):
        if num % 2 != 0 and num < smallest_odd_in:
            smallest_odd_in = num
            index_smallest_odd_in = i

    largest_even_out = -1
    if even_index < len(even_numbers):
        largest_even_out = even_numbers[even_index]

    if smallest_odd_in != float('inf') and largest_even_out != -1:
        potential_sum = current_sum - smallest_odd_in + largest_even_out
        if potential_sum % 2 == 0:
            reduction = smallest_odd_in - largest_even_out
            if reduction < min_sum_reduction:
                min_sum_reduction = reduction
                best_even_sum = potential_sum

    # Try swapping smallest even in subsequence with largest odd out of subsequence
    smallest_even_in = float('inf')
    index_smallest_even_in = -1
    for i, num in enumerate(current_subsequence):
        if num % 2 == 0 and num < smallest_even_in:
            smallest_even_in = num
            index_smallest_even_in = i

    largest_odd_out = -1
    if odd_index < len(odd_numbers):
        largest_odd_out = odd_numbers[odd_index]

    if smallest_even_in != float('inf') and largest_odd_out != -1:
        potential_sum = current_sum - smallest_even_in + largest_odd_out
        if potential_sum % 2 == 0:
            reduction = smallest_even_in - largest_odd_out
            if reduction < min_sum_reduction:
                min_sum_reduction = reduction
                best_even_sum = potential_sum

    return best_even_sum

Big(O) Analysis

Time Complexity

O(n log n) – The initial separation of numbers into even and odd groups takes O(n) time. Sorting these groups, specifically the odd numbers, to efficiently find the smallest and largest relevant elements for potential swaps dominates the complexity, leading to O(n log n) in the worst case if all numbers are odd. The selection and potential swapping process involves a constant number of operations or a fixed number of swaps (at most two rounds of swaps), which is O(1) after sorting. Therefore, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(n) – The algorithm requires auxiliary space to store the separate lists of even and odd numbers. In the worst case, all numbers could be even or all could be odd, leading to auxiliary lists that can store up to N elements in total. The operations of finding the smallest odd/even numbers to swap, and storing intermediate subsequences, also contribute to this auxiliary space, which is proportional to the input size N.

Edge Cases

Case	How to Handle
k is larger than the number of elements in nums	The problem constraints imply k will not exceed nums. If it could, return -1 as no subsequence of size k can be formed.
nums is empty or null	Return -1 immediately if nums is null or empty, as no subsequence can be formed.
k is zero or negative	Return -1 if k is zero or negative, as a subsequence of non-positive size is not meaningful in this context.
No subsequence of size k can form an even sum	The algorithm will naturally result in -1 if no combination of k elements yields an even sum.
All numbers in nums are odd	If k is odd, an even sum is impossible; if k is even, an even sum might be possible using pairs of odd numbers.
All numbers in nums are even	Any subsequence of size k will have an even sum, so we need to pick the k largest numbers.
nums contains zeros	Zeros do not affect the parity of the sum but can be part of the largest sum subsequence if they are among the largest elements.
nums contains negative numbers	Negative numbers can be included if they contribute to the largest possible even sum, requiring careful sorting and selection.

k is larger than the number of elements in nums

How to Handle:

The problem constraints imply k will not exceed nums. If it could, return -1 as no subsequence of size k can be formed.

nums is empty or null

How to Handle:

Return -1 immediately if nums is null or empty, as no subsequence can be formed.

k is zero or negative

How to Handle:

Return -1 if k is zero or negative, as a subsequence of non-positive size is not meaningful in this context.

No subsequence of size k can form an even sum

How to Handle:

The algorithm will naturally result in -1 if no combination of k elements yields an even sum.

All numbers in nums are odd

How to Handle:

If k is odd, an even sum is impossible; if k is even, an even sum might be possible using pairs of odd numbers.

All numbers in nums are even

How to Handle:

Any subsequence of size k will have an even sum, so we need to pick the k largest numbers.

nums contains zeros

How to Handle:

Zeros do not affect the parity of the sum but can be part of the largest sum subsequence if they are among the largest elements.

nums contains negative numbers

How to Handle:

Negative numbers can be included if they contribute to the largest possible even sum, requiring careful sorting and selection.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the integer `k`?
Can the elements in `nums` be negative, zero, or only positive integers?
What should be returned if no subsequence of size `k` with an even sum can be formed? Is it always -1, or can it be something else?
Does the order of elements in the input array `nums` matter, or can we assume it's unsorted?
If there are multiple subsequences of size `k` that yield the largest possible even sum, does it matter which one we choose, or should we return a specific one based on some criteria (e.g., lexicographically smallest)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every single way to pick the required number of items from the collection.
For each group of items you've picked, calculate their total sum.
Check if that total sum is an even number.
If the sum is even, compare it to the largest even sum you've found so far.
If the current sum is larger than the best one you've seen, remember it as the new largest even sum.
After you have looked at all possible combinations of items, the largest even sum you've recorded is your answer.

Code Implementation

import itertoolsdef find_largest_even_subsequence_sum(numbers, subsequence_size):    largest_even_sum_found = -1    all_combinations = itertools.combinations(numbers, subsequence_size)    # We need to iterate through every possible group of numbers to check their sums.    for current_combination in all_combinations:        current_sum = sum(current_combination)        # Ensure the sum is even before considering it as a potential largest even sum.        if current_sum % 2 == 0:            # If the current even sum is greater than what we've seen, update our record.            if current_sum > largest_even_sum_found:                largest_even_sum_found = current_sum    # If no even sum was found, it remains -1. Otherwise, it holds the largest one.    return largest_even_sum_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Separate all the numbers into two groups: one for even numbers and one for odd numbers.
Initially, pick the largest numbers from both groups to form a preliminary subsequence. Aim to fill the required size with the biggest numbers available.
Calculate the sum of this preliminary subsequence. If the sum is already even, and we used the largest possible numbers to reach the required size, we are done.
If the sum is odd, we need to make a change. To change an odd sum to an even sum, we must change an odd number of odd numbers in our subsequence. The simplest way to do this with minimal impact on the sum is to swap one odd number with one even number.
Consider swapping the smallest odd number we included with the largest odd number we left out. Or, consider swapping the smallest even number we included with the largest even number we left out.
Choose the swap that results in the largest possible sum that is now even. If no such swap is possible that maintains the required subsequence size, it means we cannot achieve an even sum for that size with the given numbers.
If we can make a valid swap, update the subsequence and its sum. If the sum is still odd after considering all the best swaps, repeat the swapping process, trying to make the smallest possible reduction in the sum to achieve an even result.
If at any point we cannot form a subsequence of the required size, or if we exhaust all possibilities to make the sum even, then a solution doesn't exist.

Code Implementation

def largest_even_sum_subsequence(input_numbers, subsequence_size):
    even_numbers = sorted([num for num in input_numbers if num % 2 == 0], reverse=True)
    odd_numbers = sorted([num for num in input_numbers if num % 2 != 0], reverse=True)

    current_subsequence = []
    current_sum = 0

    # Greedily pick largest numbers first to maximize sum
    even_index = 0
    odd_index = 0

    while len(current_subsequence) < subsequence_size:
        if even_index < len(even_numbers) and odd_index < len(odd_numbers):
            if even_numbers[even_index] > odd_numbers[odd_index]:
                current_subsequence.append(even_numbers[even_index])
                current_sum += even_numbers[even_index]
                even_index += 1
            else:
                current_subsequence.append(odd_numbers[odd_index])
                current_sum += odd_numbers[odd_index]
                odd_index += 1
        elif even_index < len(even_numbers):
            current_subsequence.append(even_numbers[even_index])
            current_sum += even_numbers[even_index]
            even_index += 1
        elif odd_index < len(odd_numbers):
            current_subsequence.append(odd_numbers[odd_index])
            current_sum += odd_numbers[odd_index]
            odd_index += 1
        else:
            # Not enough numbers to form the subsequence
            return -1

    # If the initial sum is even, we found the optimal subsequence
    if current_sum % 2 == 0:
        return current_sum

    # If the sum is odd, we need to make swaps to make it even
    # The goal is to minimize the reduction in sum while achieving an even sum.

    min_sum_reduction = float('inf')
    best_even_sum = -1

    # Try swapping smallest odd in subsequence with largest even out of subsequence
    smallest_odd_in = float('inf')
    index_smallest_odd_in = -1
    for i, num in enumerate(current_subsequence):
        if num % 2 != 0 and num < smallest_odd_in:
            smallest_odd_in = num
            index_smallest_odd_in = i

    largest_even_out = -1
    if even_index < len(even_numbers):
        largest_even_out = even_numbers[even_index]

    if smallest_odd_in != float('inf') and largest_even_out != -1:
        potential_sum = current_sum - smallest_odd_in + largest_even_out
        if potential_sum % 2 == 0:
            reduction = smallest_odd_in - largest_even_out
            if reduction < min_sum_reduction:
                min_sum_reduction = reduction
                best_even_sum = potential_sum

    # Try swapping smallest even in subsequence with largest odd out of subsequence
    smallest_even_in = float('inf')
    index_smallest_even_in = -1
    for i, num in enumerate(current_subsequence):
        if num % 2 == 0 and num < smallest_even_in:
            smallest_even_in = num
            index_smallest_even_in = i

    largest_odd_out = -1
    if odd_index < len(odd_numbers):
        largest_odd_out = odd_numbers[odd_index]

    if smallest_even_in != float('inf') and largest_odd_out != -1:
        potential_sum = current_sum - smallest_even_in + largest_odd_out
        if potential_sum % 2 == 0:
            reduction = smallest_even_in - largest_odd_out
            if reduction < min_sum_reduction:
                min_sum_reduction = reduction
                best_even_sum = potential_sum

    return best_even_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
k is larger than the number of elements in nums	The problem constraints imply k will not exceed nums. If it could, return -1 as no subsequence of size k can be formed.
nums is empty or null	Return -1 immediately if nums is null or empty, as no subsequence can be formed.
k is zero or negative	Return -1 if k is zero or negative, as a subsequence of non-positive size is not meaningful in this context.
No subsequence of size k can form an even sum	The algorithm will naturally result in -1 if no combination of k elements yields an even sum.
All numbers in nums are odd	If k is odd, an even sum is impossible; if k is even, an even sum might be possible using pairs of odd numbers.
All numbers in nums are even	Any subsequence of size k will have an even sum, so we need to pick the k largest numbers.
nums contains zeros	Zeros do not affect the parity of the sum but can be part of the largest sum subsequence if they are among the largest elements.
nums contains negative numbers	Negative numbers can be included if they contribute to the largest possible even sum, requiring careful sorting and selection.

k is larger than the number of elements in nums

How to Handle:

The problem constraints imply k will not exceed nums. If it could, return -1 as no subsequence of size k can be formed.

nums is empty or null

How to Handle:

Return -1 immediately if nums is null or empty, as no subsequence can be formed.

k is zero or negative

How to Handle:

Return -1 if k is zero or negative, as a subsequence of non-positive size is not meaningful in this context.

No subsequence of size k can form an even sum

How to Handle:

The algorithm will naturally result in -1 if no combination of k elements yields an even sum.

All numbers in nums are odd

How to Handle:

If k is odd, an even sum is impossible; if k is even, an even sum might be possible using pairs of odd numbers.

All numbers in nums are even

How to Handle:

Any subsequence of size k will have an even sum, so we need to pick the k largest numbers.

nums contains zeros

How to Handle:

Zeros do not affect the parity of the sum but can be part of the largest sum subsequence if they are among the largest elements.

nums contains negative numbers

How to Handle:

Negative numbers can be included if they contribute to the largest possible even sum, requiring careful sorting and selection.