Python में ताजा डोनट्स पाने वाले समूहों की अधिकतम संख्या ज्ञात करें

डोनट्स बैच आकार batchSize में बनते हैं। ग्राहक समूह groups[i] आकार के हैं। नियम: एक बैच के सभी डोनट्स अगले बैच से पहले परोसे जाने चाहिए। प्रत्येक ग्राहक को एक डोनट मिलता है। समूह खुश होता है यदि उसका पहला ग्राहक ताजा डोनट (नया बैच) पाता है। समूहों को पुनर्व्यवस्थित करके खुश समूहों की अधिकतम संख्या खोजें।

एल्गोरिदम: DP + स्टेट कम्प्रेशन

1. प्रत्येक समूह आकार को batchSize से मॉड्यूलो लें (केवल शेष मायने रखता है)
2. प्रत्येक शेष की आवृत्ति गिनें
3. DP स्टेट: (current_remainder, remaining_counts)
4. पुनरावर्ती: प्रत्येक संभावित अगला समूह आज़माएं, अधिकतम खुश समूह खोजें

Python कार्यान्वयन

from collections import Counter
from functools import lru_cache

def max_happy_groups(batchSize, groups):
    # प्रत्येक समूह को मॉड्यूलो batchSize
    remainders = [g % batchSize for g in groups]
    count = Counter(remainders)
    
    # स्टेट टपल: count[0], count[1], ..., count[batchSize-1]
    initial_state = tuple(count[i] for i in range(batchSize))
    
    @lru_cache(None)
    def dp(remainder, state):
        """remainder: वर्तमान बैच में बचे डोनट्स
           state: प्रत्येक शेष के शेष समूहों की गिनती"""
        if max(state) == 0:
            return 0
        
        best = 0
        state_list = list(state)
        
        for k in range(batchSize):
            if state_list[k] == 0:
                continue
            
            state_list[k] -= 1
            # नया शेष: (remainder + k) % batchSize
            new_remainder = (remainder + k) % batchSize
            # खुश यदि नया बैच शुरू (remainder == 0)
            happy = dp(new_remainder, tuple(state_list)) + (1 if remainder == 0 else 0)
            best = max(best, happy)
            state_list[k] += 1
        
        return best
    
    return dp(0, initial_state)

# परीक्षण
batchSize = 4
groups = [2, 1, 8, 4, 3]
print(max_happy_groups(batchSize, groups))  # 4

व्याख्या (batchSize=4, groups=[2,1,8,4,3])

मॉड्यूलो 4: [2, 1, 0, 0, 3] → गिनती: {0:2, 1:1, 2:1, 3:1}

इष्टतम क्रम: [8, 4, 2, 3, 1] → मॉड्यूलो: [0, 0, 2, 3, 1]

• समूह 8 (0): नया बैच शुरू → खुश, शेष=0
• समूह 4 (0): नया बैच शुरू → खुश, शेष=0
• समूह 2 (2): शेष=2
• समूह 3 (3): (2+3)%4=1, शेष=1
• समूह 1 (1): (1+1)%4=2, शेष=2

कुल खुश: 4

जटिलता

• स्टेट स्पेस: O(batchSize × Π(count[i]+1)) - छोटे batchSize के लिए संभव
• समय: स्टेट्स × batchSize
• batchSize ≤ 9 के लिए व्यावहारिक (LeetCode कंस्ट्रेंट)

अनुकूलन: शेष 0 वाले समूह

count[0] वाले समूह हमेशा खुश होते हैं (नया बैच शुरू करते हैं)। उन्हें अलग से गिनें और DP से बाहर रखें:

base_happy = count[0]
# count[0] = 0 सेट करके DP चलाएं
# अंत में base_happy जोड़ें