Giving a list of numbers A, the goal is to find the minimum possible number of divisions you can do on each item to get an x in which x <= sum(A)/2.

For example,

• if A = [10,10] you can divide the A[0] by 2 and you can divide A[1] by 2 as well to get half of the sum of the list. So, the minimum possible number of divisions equals to 2,
• if A = [200, 25,25,25] you can divide A[0]/2^3 so x =[25,25,25,25] which sum to 100<= 275 so minimum possible number of divisions equals to 3.

I tried the following way and it works just fine, but when I input huage lists like this get_f([200,25,25,25,490,99999, 2000, 43002]) I got timeout error.

import itertools

def get_f(A):
    
  A = sorted(A)[::-1]
  Goal = sum(A)/2

  filters = []
  x = itertools.product(range(len(A)), repeat=len(A))
  for i in x:
    i = list(i)
    C = A.copy()
    x = 0
    for Index in i:
      C[Index]/=2
      x =1
      if sum(C) <= Goal and x not in filters:
        filters.append(x)
  return sorted(filters)[0]

CodePudding user response：

The currently accepted solution is incorrect- it will, for instance, never return a number larger than the length of the input list, regardless of how large any of those numbers are.

The optimal way to approach this problem is with a priority queue- allowing you to avoid recomputing the max() (as done in another answer) over and over.

Code:

from heapq import heapify, heappop, heappush
from itertools import count
from math import isclose

def solve(nums):
    heap = [-x for x in nums]
    heapify(heap)

    total = sum(nums)
    target = total / 2

    for divs in count():
        if total < target or isclose(total, target):
            return divs
        
        delta = heappop(heap) / 2
        total  = delta
        heappush(heap, delta)

Demo:

>>> print(solve([200, 25, 25, 25]))
2
>>> print(solve([200, 25, 25, 25, 0]))
2
>>> print(solve([100, 25, 100, 25]))
3

Note: the original example in the problem statement is wrong- you can divide 200 by 2 twice, and the sum [50, 25, 25, 25] = 125 is less than the original sum 275, making the answer 2, not 3.

CodePudding user response：

Here is my version of the code. It works just fine on the tests. Check it out.

def get_f(A):
    """
    A: list of numbers
    return: int
    """
    x = sum(A) // 2
    if x == 0:
        return 0
    count = 0
    for i in A:
        if i <= x:
            count  = 1
    return count

print(get_f([10,10]))
print(get_f([200, 25,25,25]))
print(get_f([10,10,10]))
print(get_f([10,10,10,10]))
print(get_f([200,25,25,25,490,99999, 2000, 43002]))

Hope this is what you were looking for

CodePudding user response：

def get_f(xs):
    goal = sum(xs) / 2
    f = 0
    while sum(xs) > goal:
        i = xs.index(max(xs))
        xs[i] /= 2
        f  = 1
    return f

This should work in case it's okay to mutate the input list.