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

user_14148536 0
Viewed 2750

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.

arrays algorithm python
1 Answers

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 odd 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.

user_5726700
Related