# Can you provide a better optimized algorithm for this code

3792 views
7

QUESTION - There are N stalls in a vegetable market that are selling vegetables. You have to buy an equal amount of vegetables from each stall. If a stall does not have enough vegetables to offer, then you have to buy all the vegetables available in that stall. If you are given the number of vegetables that every stall can offer, determine the minimum quantity that you need to buy from each stall such that you have at least K vegetables in total.

Input format

First line: Integer N denoting the number of stalls Next line: N space-separated integers and quan(subscript i) denoting the i^th integer which determines the quantity of vegetables that i^th stall would be offering Next line: Integer Q denoting the number of queries Next Q lines: Integer K(subscript i) denoting the minimum amount of vegetables needed in total Output format

For each query, print the minimum quantity of vegetables that you have to buy from each shop in a new line. Print -1 if it is not possible to buy the required number of vegetables.

Sample Input 5 3 8 4 1 7 5 13 19 3 25 22 Sample Output 3 6 1 -1 7 Explanation Query 1: By taking 3 vegetables from every stall, we get 3+3+3+1+3=13. If we take 2 vegetables, we would get 2+2+2+1+2=9.

Query 2: By taking 6 from each stall, we get 3+6+4+1+6=20.

Query 4: Even if we take all from every shop, we would have 3+8+4+1+7. Hence the answer is -1.

CODE-

``````from math import ceil
t = int(input())
arr = map(int,input().split())
arr = sorted(arr)
sumo = sum(arr)
q = int(input())
for _ in  range(q):
quantity = int(input())
if sumo<quantity:
ans = -1
elif sumo==quantity:
ans = max(arr)
else:
if quantity==0:
ans = 0
else:
for i in range(t):
temp = ceil(quantity/(t-i))
if temp==arr[i]:
ans = temp
break
elif temp>arr[i]:
quantity-=arr[i]
ans = arr[i]
else:
ans=temp
break
``````

print(ans)

test case-

5 3 8 4 1 7 5 13 19 3 25 22 output-

3 6 1 -1 7

What problems are you having trying to optimise this code? From the help centre: "Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it."

3

I am working on it. Give me two days and I'll definitely find an answer

posted this