পাইথনে লগ ট্রানকেট করে ডেটাবেসে স্টোর করার সর্বোচ্চ সাইজ খুঁজে বের করার প্রোগ্রাম

একটি লগ সাইজের তালিকা logs এবং একটি limit দেওয়া আছে। logs[i] = i-তম ইউজারের লগ সাইজ। সব লগকে সর্বোচ্চ সাইজ x এ ট্রানকেট করলে (যেমন লগ > x হলে x করুন) মোট সমষ্টি limit-এর নিচে থাকতে হবে। সবচেয়ে বড় এমন x বের করুন। যদি কোনো লগ ট্রানকেট লাগে না, তবে সবচেয়ে বড় লগ সাইজ রিটার্ন করুন।

উদাহরণ: logs = [500, 200, 10000, 500, 4000], limit = 3000 হলে আউটপুট 900। কারণ ট্রানকেট করলে [500, 200, 900, 500, 900] হয়, যোগফল = ৩০০০।

সমাধানের পদ্ধতি

বাইনারি সার্চ ব্যবহার করুন x-এর ওপর। সার্চ স্পেস: [0, max(logs) + 1]।

• mid দিয়ে ট্রানকেট করলে যোগফল sum(min(mid, log) for log in logs)।
• যদি যোগফল ≤ limit, তবে mid বড় করা যেতে পারে → lo = mid।
• অন্যথায় hi = mid।
• lo + 1 < hi পর্যন্ত চলান।

পাইথন কোড

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

সময় জটিলতা

O(n log M) - n = লগ সংখ্যা, M = max(logs)। বাইনারি সার্চ O(log M), প্রতিটি চেক O(n)।