python getting the largest even sum of an array with k elements

user14148536 :

I've been studying python algorithm and would like to solve a problem that is:

  1. A positive integer array A and an integer K are given.
  2. Find the largest even sum of the array A with K elements.
  3. If not possible, return -1.

For example, if there is an array A= [1,2,3,4,4,5] and K= 3, the answer is 12 (5+4+3), which is the largest even sum with K (3) elements. However, if A= [3, 3, 3] and K= 1, the answer is -1 because it cannot make an even sum with one element.

I tried to exclude every minimum odd from the array, but it failed when K=n in the while loop. Is there any simple way to solve this problem? I would sincerely appreciate if you could give some advice.

amit :

Sort the array and "take" the biggest K elements.

If it's already even sum - you are done.

Otherwise, you need to replace exactly one element, replace an even element you have chosen with an odd one you have not, or the other way around. You need the difference between the two elements to be minimized.

A naive solution will check all possible ways to do that, but that's O(n^2). You can do better, by checking the actual two viable candidates:

  • The maximal odd element you did not choose, and the minimal even element you have chosen
  • The maximal even element you did not choose and the minimal even element you have chosen.

Choose the one that the difference between the two elements is minimal. If no such two elements exist (i.e. your k=3, [3,3,3] example) - there is no viable solution.

Time complexity is O(nlogn) for sorting.

In my (very rusty) python, it should be something like:

def FindMaximalEvenArray(a, k):
    a = sorted(a)
    chosen = a[len(a)-k:]
    not_chosen = a[0:len(a)-k]
    
    if sum(chosen) % 2 == 0:
        return sum(chosen)
    
    smallest_chosen_even = next((x for x in chosen if x % 2 == 0), None)
    biggest_not_chosen_odd = next((x for x in not_chosen[::-1] if x % 2 != 0), None)    
    candidiate1 = smallest_chosen_even - biggest_not_chosen_odd  if smallest_chosen_even and biggest_not_chosen_odd else float("inf")

    smallest_chosen_odd = next((x for x in chosen if x % 2 != 0), None)
    biggest_not_chosen_even = next((x for x in not_chosen[::-1] if x % 2 == 0), None)
    candidiate2 = smallest_chosen_odd - biggest_not_chosen_even  if smallest_chosen_odd and biggest_not_chosen_even else float("inf")

    if candidiate1 == float("inf") and candidiate2 == float("inf"):
        return -1
    return sum(chosen) - min(candidiate1, candidiate2)

Note: This can be done even better (in terms of time complexity), because you don't actually care for the order of all elements, only finding the "candidates" and the top K elements. So you could use Selection Algorithm instead of sorting, which will make this run in O(n) time.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

Getting the largest k elements of a double array

Largest k elements in array under contraints

K largest elements of an array, sorting algorithm

Largest subset in an array such that the smallest and largest elements are less than K apart

Sum of elements in array using recursion even if they are string

What is the fastest way to get k smallest (or largest) elements of array in Java?

Finding the K UNIQUE largest elements in an unsorted array of pairs

How to improve this code for finding the k largest elements of an array?

How do I return the sum of the three largest elements in an array?

Largest sum from absolute differences of N elements in an array

sum of array elements(any order) equal to k not continuous elements

Optimal algorithm to return largest k elements from an array of infinite number of elements in running stream

Sort elements only at even indices of an array, in python

Kth largest number in an array using "Sort K number of elements based array" algorithm

maximum no. of elements in an array having sum less than or equal to k

Find sum of largest subset of array

largest sum of contiguous subarray No Larger than k

Getting Sum of 3D Array elements by using pointer

Getting Largest Number From Array

Calculate the sum of every 5 elements in a python array

Editing the sum of array elements to equal a value in Python

Find the first and last indices of an array for which the sequential sum of elements from and to will be the largest

Find the three largest elements in an array

Finding largest elements in array efficiently

find the n largest elements in an array

Finding the three largest elements in an array

Swap largest and last elements in array

Product of largest elements in 2 array

"Stable" k-largest elements algorithm