पायथन में K-आकार के ग्रुप्स की अधिकतम संख्या खोजने का प्रोग्राम जहां प्रत्येक ग्रुप में विशिष्ट प्रकार के आइटम हों

मान लीजिए हमारे पास counts नामक संख्याओं की एक सूची है जहां counts[i] टाइप i के आइटम की संख्या दर्शाता है। हमारे पास एक और मान k भी है। हमें आकार k के ग्रुप्स की अधिकतम संख्या ढूंढनी है, जैसे कि प्रत्येक ग्रुप में विशिष्ट प्रकार के आइटम हों।

उदाहरण के लिए, यदि इनपुट है counts = [2, 3, 5, 3], k = 2, तो आउटपुट 6 होगा, क्योंकि चार प्रकार के आइटम को a, b, c, d से दर्शाया गया है। हमारे पास k=2 के निम्नलिखित ग्रुप हो सकते हैं, जहां सभी तत्व विशिष्ट प्रकार के हैं: [(c, a), (b, a), (c, b), (c, b), (d, a), (d, a)]।

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

possible(counts, groups, k) फ़ंक्शन परिभाषित करें:
- required := groups * k
- प्रत्येक i के लिए 0 से len(counts)-1 तक:
  - temp := min(counts[i], groups, required)
  - required := required - temp
  - यदि required == 0, तो True लौटाएं
- False लौटाएं
solve(counts, k) फ़ंक्शन परिभाषित करें:
- res := 0, l := 0, r := sum(counts)
- while l <= r:
  - m := l + (r - l) // 2
  - यदि possible(counts, m, k) True है, तो l := m + 1, res := max(res, m)
  - अन्यथा, r := m - 1
- res लौटाएं

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

def possible(counts, groups, k):
    required = groups * k
    for i in range(len(counts)):
        temp = min(counts[i], groups, required)
        required -= temp
        if required == 0:
            return True
    return False

def solve(counts, k):
    res = 0
    l = 0
    r = sum(counts)
    while l <= r:
        m = l + (r - l) // 2
        if possible(counts, m, k):
            l = m + 1
            res = max(res, m)
        else:
            r = m - 1
    return res

counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k))  # आउटपुट: 6

इनपुट

[2, 3, 5, 3], 2