पायथन में लॉग्स को डेटाबेस में पूरी तरह स्टोर करने के लिए सबसे बड़े ट्रंकेट साइज को खोजने का प्रोग्राम

मान लीजिए हमारे पास logs नामक संख्याओं की एक सूची है और एक मान limit है। logs[i में प्रत्येक तत्व i-वें उपयोगकर्ता द्वारा उत्पन्न लॉग्स का आकार दर्शाता है। और limit उस कुल आकार को दर्शाता है जिसे हम अपने डेटाबेस में स्टोर कर सकते हैं। हमें सबसे बड़ा x ढूंढना है जैसे कि यदि हम logs में हर लॉग को अधिकतम आकार x तक ट्रंकेट करते हैं, और शेष लॉग आकारों का योग अधिकतम limit है। यदि किसी लॉग को ट्रंकेट करने की आवश्यकता नहीं है, तो बस सबसे बड़ा लॉग आकार लौटाएं।

उदाहरण के लिए, यदि इनपुट है logs = [500, 200, 10000, 500, 4000], limit = 3000, तो आउटपुट 900 होगा, क्योंकि हम लॉग्स को 900 तक ट्रंकेट करते हैं, तो हमें [500, 200, 900, 500, 900] मिलता है अब योग 3000 है।

एल्गोरिदम (बाइनरी सर्च)

lo := 0
hi := 1 + max(logs)
while lo + 1 < hi:
- mi := lo + (hi - lo) // 2
- यदि sum(min(mi, log) for log in logs) <= limit, तो lo := mi
- अन्यथा, hi := mi
lo लौटाएं

उदाहरण कार्यान्वयन

def solve(logs, limit):
    lo, hi = 0, max(logs) + 1
    while lo + 1 < hi:
        mi = lo + (hi - lo) // 2
        if sum(min(mi, log) for log in logs) <= limit:
            lo = mi
        else:
            hi = mi
    return lo

logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit))  # आउटपुट: 900

इनपुट

[500, 200, 10000, 500, 4000], 3000