Jobs

Interviews

Discussions

Subsequence of Size K With the Largest Even Sum

Medium

Asked by:

0 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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:

0 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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 `nums` array and the value of `k`?
Can the input array `nums` contain negative numbers, and if so, how should they be handled?
What should be returned if no subsequence of length `k` exists that results in an even sum?
Are duplicate numbers allowed in the `nums` array, and how do they affect the selection of the subsequence?
If multiple subsequences of length `k` yield the same maximum even sum, is any one of them acceptable?

Brute Force Solution

Approach

The brute force approach is all about trying absolutely everything! For this problem, we need to find the best group of numbers of a specific size that adds up to an even number. We will explore every possible combination of numbers until we find the best one.

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

First, consider all the possible groups of numbers you can make from the original list. Make sure each group has the required size.
Next, for each of these groups, calculate the sum of all the numbers in that group.
Then, check if the sum you just calculated is an even number. If it is not, discard that group.
If the sum is even, compare that sum to the largest even sum you have found so far. If the current sum is bigger, remember it and the group that created it.
Keep doing this for every possible group of numbers of the specified size.
Finally, after you have gone through all the groups, the largest even sum you remembered is the answer, and the group that created it is the subsequence we were looking for.

Code Implementation

def find_largest_even_sum_brute_force(numbers, k):
    all_even_sums = []
    number_of_numbers = len(numbers)

    # Iterate through all possible combinations of k numbers
    for i in range(1 << number_of_numbers):
        current_combination = []
        for j in range(number_of_numbers):
            if (i >> j) & 1:
                current_combination.append(numbers[j])

        if len(current_combination) == k:
            sum_of_combination = sum(current_combination)

            # Check if the sum is even
            if sum_of_combination % 2 == 0:

                # Store the even sum
                all_even_sums.append(sum_of_combination)

    # Find the largest even sum from all combinations
    if not all_even_sums:
        return -1
    else:
        return max(all_even_sums)

Big(O) Analysis

Time Complexity

O(n^k) – The algorithm iterates through all possible subsequences of size k from the input array of size n. The number of such subsequences is given by the binomial coefficient 'n choose k', which is n! / (k! * (n-k)!). In the worst case, it needs to consider all combinations. Since k is a factor in determining the number of combinations this yields to a runtime of O(n^k) due to iterating over all possible subsequences. Each combination requires computing a sum of k elements, but this does not change the O(n^k) complexity.

Space Complexity

O(1) – The brute force approach, as described, considers all possible subsequences of size K. It maintains a variable to store the largest even sum found so far, and potentially another variable to store the corresponding subsequence. The space used to store these variables (the largest even sum and potentially the best subsequence) is independent of the input size N (the size of the original list). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The goal is to find the 'k' numbers from the given list that add up to the largest possible even number. We achieve this by prioritizing even numbers and strategically handling odd numbers to ensure the sum remains even and maximized.

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

Separate the numbers into two groups: even numbers and odd numbers.
Sort both the even and odd number groups in descending order (from largest to smallest). This way, we pick the biggest numbers first.
Take as many even numbers as possible, but no more than 'k' of them. Even numbers guarantee an even sum, and we want the biggest ones.
Calculate how many more numbers we need to reach 'k'. This tells us how many odd numbers we might need to use.
If we need an even number of odd numbers, take the biggest ones from the sorted odd numbers list. This keeps the total count at 'k' and makes the sum even.
If we need an odd number of odd numbers (say one odd number), we need to be clever: consider two options. Either replace the smallest even number with one of the biggest odd numbers, or replace the two smallest odd numbers from our initially selected group with a potentially bigger even number. Pick the swap that gives you the largest sum.
If we don't have enough numbers of one kind to swap, skip the respective step.
The final set of 'k' numbers will give you the largest possible even sum.

Code Implementation

def find_largest_even_subsequence(number_list, subsequence_size):
    even_numbers = sorted([number for number in number_list if number % 2 == 0], reverse=True)
    odd_numbers = sorted([number for number in number_list if number % 2 != 0], reverse=True)

    max_sum = -1

    # Check if we can form a subsequence using only even numbers.
    if len(even_numbers) >= subsequence_size:
        max_sum = sum(even_numbers[:subsequence_size])

    # Iterate to find the best combination of even and odd numbers.
    for odd_numbers_count in range(min(len(odd_numbers) + 1, subsequence_size + 1)):
        if odd_numbers_count % 2 == 0:
            continue

        #Ensure total number of items does not exceed the list
        even_numbers_count = subsequence_size - odd_numbers_count
        if even_numbers_count < 0 or even_numbers_count > len(even_numbers):
            continue

        current_sum = sum(odd_numbers[:odd_numbers_count]) + sum(even_numbers[:even_numbers_count])
        max_sum = max(max_sum, current_sum)

    for odd_numbers_count in range(min(len(odd_numbers) + 1, subsequence_size + 1)):
        if odd_numbers_count % 2 != 0:
            continue

        even_numbers_count = subsequence_size - odd_numbers_count

        # Ensure we don't take more evens than there are, or negative
        if even_numbers_count < 0 or even_numbers_count > len(even_numbers):
            continue

        # This iteration ensures sum is still even.
        current_sum = sum(odd_numbers[:odd_numbers_count]) + sum(even_numbers[:even_numbers_count])
        max_sum = max(max_sum, current_sum)

    # Return -1 if no valid subsequence can be found
    if max_sum == -1:
        return -1

    return max_sum

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operations in this solution are the sorting steps. We separate the input array of size 'n' into even and odd numbers, which takes O(n) time. Then, we sort both the even and odd arrays using an efficient sorting algorithm like merge sort or quicksort, each taking O(m log m) and O((n-m) log (n-m)) time respectively, where 'm' is the number of even numbers. Since sorting dominates the linear separation, and m <= n, the overall time complexity is O(n log n) because the sum of O(m log m) + O((n-m) log (n-m)) is bounded by O(n log n). The remaining operations like calculating sums and comparisons take at most O(k) time, and because k <= n, these operations are less significant than the sorting.

Space Complexity

O(N) – The algorithm creates two lists, one for even numbers and one for odd numbers. In the worst-case scenario, all N input numbers are either even or odd, leading to an auxiliary space proportional to N. Sorting these lists in place does not change the auxiliary space, but creating new sorted lists would. Therefore, the space complexity is O(N) because the algorithm needs to store, at most, all N elements in either the even or odd list temporarily, before in place sorting can happen.

Edge Cases

Case	How to Handle
Null or empty input array nums	Return -1 immediately as no subsequence can be formed.
k is 0	Return 0 since an empty subsequence has sum 0, which is even.
k is greater than the length of nums	Return -1 immediately, as a subsequence of length k cannot be formed.
Array contains only odd numbers and k is odd	No even sum is possible; return -1 if no even subsequence sum can be created.
Array contains only odd numbers and k is even	No even sum is possible; return -1.
Array contains only negative odd numbers and k is even	Return the largest possible negative even sum if k <= len(nums), and -1 otherwise.
Array contains only negative odd numbers and k is odd	Return -1 as no positive or zero result is possible and the question requires a maximum even sum.
Integer overflow if sum is very large	Use long data type to store intermediate sums.

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 `nums` array and the value of `k`?
Can the input array `nums` contain negative numbers, and if so, how should they be handled?
What should be returned if no subsequence of length `k` exists that results in an even sum?
Are duplicate numbers allowed in the `nums` array, and how do they affect the selection of the subsequence?
If multiple subsequences of length `k` yield the same maximum even sum, is any one of them acceptable?

Brute Force Solution

Approach

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

First, consider all the possible groups of numbers you can make from the original list. Make sure each group has the required size.
Next, for each of these groups, calculate the sum of all the numbers in that group.
Then, check if the sum you just calculated is an even number. If it is not, discard that group.
If the sum is even, compare that sum to the largest even sum you have found so far. If the current sum is bigger, remember it and the group that created it.
Keep doing this for every possible group of numbers of the specified size.
Finally, after you have gone through all the groups, the largest even sum you remembered is the answer, and the group that created it is the subsequence we were looking for.

Code Implementation

def find_largest_even_sum_brute_force(numbers, k):
    all_even_sums = []
    number_of_numbers = len(numbers)

    # Iterate through all possible combinations of k numbers
    for i in range(1 << number_of_numbers):
        current_combination = []
        for j in range(number_of_numbers):
            if (i >> j) & 1:
                current_combination.append(numbers[j])

        if len(current_combination) == k:
            sum_of_combination = sum(current_combination)

            # Check if the sum is even
            if sum_of_combination % 2 == 0:

                # Store the even sum
                all_even_sums.append(sum_of_combination)

    # Find the largest even sum from all combinations
    if not all_even_sums:
        return -1
    else:
        return max(all_even_sums)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Separate the numbers into two groups: even numbers and odd numbers.
Sort both the even and odd number groups in descending order (from largest to smallest). This way, we pick the biggest numbers first.
Take as many even numbers as possible, but no more than 'k' of them. Even numbers guarantee an even sum, and we want the biggest ones.
Calculate how many more numbers we need to reach 'k'. This tells us how many odd numbers we might need to use.
If we need an even number of odd numbers, take the biggest ones from the sorted odd numbers list. This keeps the total count at 'k' and makes the sum even.
If we need an odd number of odd numbers (say one odd number), we need to be clever: consider two options. Either replace the smallest even number with one of the biggest odd numbers, or replace the two smallest odd numbers from our initially selected group with a potentially bigger even number. Pick the swap that gives you the largest sum.
If we don't have enough numbers of one kind to swap, skip the respective step.
The final set of 'k' numbers will give you the largest possible even sum.

Code Implementation

def find_largest_even_subsequence(number_list, subsequence_size):
    even_numbers = sorted([number for number in number_list if number % 2 == 0], reverse=True)
    odd_numbers = sorted([number for number in number_list if number % 2 != 0], reverse=True)

    max_sum = -1

    # Check if we can form a subsequence using only even numbers.
    if len(even_numbers) >= subsequence_size:
        max_sum = sum(even_numbers[:subsequence_size])

    # Iterate to find the best combination of even and odd numbers.
    for odd_numbers_count in range(min(len(odd_numbers) + 1, subsequence_size + 1)):
        if odd_numbers_count % 2 == 0:
            continue

        #Ensure total number of items does not exceed the list
        even_numbers_count = subsequence_size - odd_numbers_count
        if even_numbers_count < 0 or even_numbers_count > len(even_numbers):
            continue

        current_sum = sum(odd_numbers[:odd_numbers_count]) + sum(even_numbers[:even_numbers_count])
        max_sum = max(max_sum, current_sum)

    for odd_numbers_count in range(min(len(odd_numbers) + 1, subsequence_size + 1)):
        if odd_numbers_count % 2 != 0:
            continue

        even_numbers_count = subsequence_size - odd_numbers_count

        # Ensure we don't take more evens than there are, or negative
        if even_numbers_count < 0 or even_numbers_count > len(even_numbers):
            continue

        # This iteration ensures sum is still even.
        current_sum = sum(odd_numbers[:odd_numbers_count]) + sum(even_numbers[:even_numbers_count])
        max_sum = max(max_sum, current_sum)

    # Return -1 if no valid subsequence can be found
    if max_sum == -1:
        return -1

    return max_sum

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array nums	Return -1 immediately as no subsequence can be formed.
k is 0	Return 0 since an empty subsequence has sum 0, which is even.
k is greater than the length of nums	Return -1 immediately, as a subsequence of length k cannot be formed.
Array contains only odd numbers and k is odd	No even sum is possible; return -1 if no even subsequence sum can be created.
Array contains only odd numbers and k is even	No even sum is possible; return -1.
Array contains only negative odd numbers and k is even	Return the largest possible negative even sum if k <= len(nums), and -1 otherwise.
Array contains only negative odd numbers and k is odd	Return -1 as no positive or zero result is possible and the question requires a maximum even sum.
Integer overflow if sum is very large	Use long data type to store intermediate sums.