Jan 2022
1 / 3
Jan 2022
Jan 2022
sksharma
Jan '22

I guess I am using the most optimal solution, don’t know what else can be optimized. Can anyone help? Thanks.

import sys
from sys import stdin, stdout
from math import sqrt,gcd
from collections import deque
sys.setrecursionlimit(10**8)
ip = lambda :stdin.readline()
I     = lambda :int(ip())
S     = lambda :ip().strip()
M     = lambda :map(int,ip().strip().split())
L     = lambda :list(map(int,ip().strip().split()))
mod=1000000007

##########################################################

def valid(m):
	if marr>=m:
		if sarr-n*m>=M:
			return True
		else:
			return False
	s=0
	for i in arr:
		if i>m:
			s+=i-m
		if s>=M:
			return True
	return False
n,M=M()
arr=L()
sarr=sum(arr)
marr=min(arr)
l,r=0,max(arr)
ans=r
while l<=r:
	m=(l+r)//2
	if valid(m):
		ans=m
		l=m+1
	else:
		r=m-1
stdout.write(str(ans))

  • created

    Jan '22

  • last reply

    Jan '22
  • 2

    replies

  • 574

    views

  • 2

    users

  • 1

    like

simes
Jan '22

OK, I don’t know Python much at all, so I might be talking rubbish, but wouldn’t each of those calls need to iterate through the whole array to return the sum, min or max? Isn’t that going to take some time when the array has 1 million elements? Would it be quicker to write an explicit loop to iterate through the array just once?

sksharma
Jan '22

Yes, your point is valid, it will take extra time, but if we talk about time complexity then it shouldn’t matter much because all these are O(n) operations. Anyways, I tried your suggestion but still tle. Maybe the compiler is not optimized for python solutions.