Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Fast binary search solution solution in Clear category for Workout by swagg010164
from typing import List
from math import ceil
def calc_sum(dopt, diffs, additional):
c = sum([ceil(k/ dopt) - 1 for k in diffs])
if c > additional:
return "too less"
if c <= additional:
return "too much"
def bin_search(start, stop, diffs, additional):
while stop - start > 1:
mid = (start + stop) // 2
res = calc_sum(mid, diffs, additional)
if res == "too less":
start = mid
elif res == "too much":
stop = mid
return stop
def workout(sessions: List[int], additional: int) -> int:
diffs = [sessions[i + 1] - sessions[i] for i in range(len(sessions) - 1)]
ans = bin_search(1, max(diffs), diffs, additional)
return ans
May 16, 2020