Maximum number of elements on list whose value sum up to at most K in O(log n)

Question

I have this exercise to do:

Let M be a positive integer, and V = ⟨v1, . . . , vn⟩ an ordered vector where the value of item vi is 5×i.

Present an O(log(n)) algorithm that returns the maximum number of items from V that can be selected given that the sum of the selected items is less than or equal to M (repeated selection of items is not allowed).

First I did a naive solution where:

• I know the sum of elements on the array will be always less than the M/5 index on the array. So a did for i=0..i<=M/5 and found the sum. Moreover this is not O(log(n)) because given a big M, bigger than the sum of all elements on the array, it will be O(n).

Therefore I tried divide and conquer, I thought a binary search should be the way. But actually no because if I do that I will sum the minimum elements that can be chosen to arrive in M, not the maximum. My code is below

   def max_items_selected_recursive2(M, V, left, right, max):

    if len(V[left:right]) == 1:
      return max
    

    mid =  math.floor((left+right)/2)
    if  V[mid] >= M:
        return max_items_selected_recursive2(M - V[mid], V, mid + 1, right, max+1)
    else:
        if  M - V[mid] >= 0:
          return max_items_selected_recursive2(M - V[mid], V, left, mid - 1, max+1)
        else: 
          return max_items_selected_recursive2(M, V, left, mid - 1, max)
   

example of call

M = 20
  V = [0, 5, 10, 15, 20]
  max_items_selected_recursive2(M, V, 0, len(V) - 1, 0) +1 # +1 since all have the O element

Any ideas on how to do this on O(log n)?

Answer 1

The sum 1 + 2 + ... + n = n * (n+1) / 2.

The sum 5 + 10 + ... + 5n = 5 * (1 + 2 + ... + n) = 5 * n * (n+1) / 2.

So given an M, we want to solve for n so that 5 * n * (n+1) / 2 <= M. Then, add 1 to this to account for zero.

You can use the quadratic formula for an O(1) (which is also O(log n)) solution, or binary search on n for an O(log n) solution.

Answer 2

Your solution is almost there. It has two flaws.

def max_items_selected_recursive2(M, V, left, right):
    if left == right:
      return left
    
    mid =  math.floor((left+right)/2) 

    arithmetic_med = 5* (mid*(mid+1)/2)

    arithmetic_med_plus_1 = 5* (mid+1*((mid+1)+1)/2)    # <--- one
    
    if arithmetic_med <= M and arithmetic_med_plus_1 >=M: # <--- two
      return mid
    elif arithmetic_med <= M:
        return max_items_selected_recursive2(M, V, mid + 1, right)
    else:
        return max_items_selected_recursive2(M, V, left, mid - 1)

First, mid+1*((mid+1)+1)/2 is not what you want. This expression takes ((mid+1)+1)/2, multiplies it by 1 (so a no-op), and then adds mid. It looks like you forgot some parentheses. What you want instead is (mid+1)*(mid+2)/2 (note adding 1 twice is the same thing as adding 2).

Second, the >= comparison is incorrect. When an exact equality is achieved, you return mid, but that's too small. The correct answer would be mid+1, because adding that many array members yields exactly M. You need to change that >= to >.