Subsequence of Size K With the Largest Even Sum LeetCode Solution

Difficulty Level Medium
Frequently asked in Microsoft
DRW RetailMeNotViews 23

Problem Statement

The Subsequence of Size K With the Largest Even Sum LeetCode Solution – “Subsequence of Size K With the Largest Even Sum” states given an array nums and an integer k, the task here is to find the largest even sum of any subsequence from array nums which is of size k.

Return the sum if it exists, else return -1.

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

Example:

Input: nums: { 5, 2, 9, 7, 7, 2}  k : 3

Output: 18

Explanation: The subsequence with an even number of the sum is [9,7,2] = 18.

Optimized Solution:

A common sense after reading this problem is to use greedy by sorting this array first. Then we can fetch elements and add them up from the largest end. The only tricky part came to the fact that once k elements were achieved, we didn’t get an even sum.

Approach: 

The key point here is Sum of n elements can be even by the combination of an even number of odd elements and the sum of two even numbers is always even.

  • Sort the array in reverse order.
  • Find the sum of the first k elements, and keep track of the smallest odd element and smallest even element.
  • If the sum is even return the sum.
  • Else traverse array from k to end, here two things come into the picture:
    • If the current element is even remove the smallest odd element from the sum and add the current element.
    • If the current element is odd remove the smallest even element from the sum and add the current element.

Subsequence of Size K With the Largest Even Sum LeetCode SolutionPin

Code:

C++ Program of Subsequence of Size K With the Largest Even Sum LeetCode Solution

class Solution {
public:
    long long largestEvenSum(vector<int>& A, int k) {
        long long sum = 0;
        int n = A.size();
        long long res = -1;
        sort(A.begin(),A.end());
        reverse(A.begin(),A.end());
        
        int curr_odd = -1;
        int curr_even = -1;
        
        for (int i = 0; i < k ;i++)
        {
           sum = sum + A[i];
           if (A[i]%2 == 0)
               curr_even = A[i];
            else
                curr_odd = A[i];
            
        }
        
        if(sum % 2 == 0)
            return sum;
        
        
        for(int i = k; i < n; i++)
        {
            if(A[i]%2 == 0 && curr_odd != -1)
                res = max(res, sum + A[i] -curr_odd);
            if(A[i]%2 != 0 && curr_even != -1)
                res = max(res, sum + A[i] - curr_even);
        }
        
        if (res % 2 == 0)
            return res;
        else
            return -1;
        
    }
};

Java Program of Subsequence of Size K With the Largest Even Sum LeetCode Solution

class Solution {
    static void reverse(int a[], int n)
    {
        int i, t;
        for (i = 0; i < n / 2; i++) {
            t = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = t;
        }
    }
    public long largestEvenSum(int[] nums, int k) {
        long sum = 0;
        int n = nums.length;
        long res = -1;
        Arrays.sort(nums);
        reverse(nums,n);
        
        int curr_odd = -1;
        int curr_even = -1;
        
        for (int i = 0; i < k ;i++)
        {
           sum = sum + nums[i];
           if (nums[i]%2 == 0)
               curr_even = nums[i];
            else
                curr_odd = nums[i];
            
        }
        
        if(sum % 2 == 0)
            return sum;
        
        
        for(int i = k; i < n; i++)
        {
            if(nums[i]%2 == 0 && curr_odd != -1)
                res = Math.max(res, sum + nums[i] -curr_odd);
            if(nums[i]%2 != 0 && curr_even != -1)
                res = Math.max(res, sum + nums[i] - curr_even);
        }
        
        if (res % 2 == 0)
            return res;
        else
            return -1;
    }
}

Complexity Analysis

Time Complexity

The Time Complexity of the above code is O(nlogn).

Space Complexity

The space Complexity of the above code is O(1).

Reference: https://en.wikipedia.org/wiki/Subsequence

Leave a Comment

Translate »