पायथन में ठीक दो आइटम वाले अच्छे भोजन की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक सरणी deli है जहां deli[i] i-वें भोजन की स्वादिष्टता है, हमें इस सूची से बनाए जा सकने वाले विभिन्न अच्छे भोजन की संख्या ज्ञात करनी है। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9 + 7 मॉड्यूलो वापस करें। यहां एक अच्छा भोजन का अर्थ है एक ऐसा भोजन जिसमें ठीक दो अलग-अलग खाद्य पदार्थ हों जिनकी स्वादिष्टता का योग दो की घात हो। हम अच्छा भोजन बनाने के लिए किन्हीं दो अलग-अलग खाद्य पदार्थों का चयन कर सकते हैं।

इसलिए, यदि इनपुट है deli = [1,7,3,6,5], तो आउटपुट 3 होगा क्योंकि हम (1,3), (1,7) और (3,5) जोड़े बना सकते हैं जिनका योग 2 की घात है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• m := 10^9 + 7
• count := प्रत्येक स्वादिष्टता मान की आवृत्ति वाला एक मैप
• ans := 0
• count में प्रत्येक item i के लिए, करें
  • n को 0 से 21 तक के लिए, करें
    • j := (2^n) - i
    • यदि j count में है, तो
      • यदि i j के समान है, तो
        • ans := ans + count[i] * (count[i]-1)
      • अन्यथा,
        • ans := ans + count[i] * count[j]
• (ans/2) का भागफल mod m वापस करें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

from collections import Counter

def solve(deli):
    m = 10**9 + 7
    count = Counter(deli)
    ans = 0
    for i in count:
        for n in range(22):
            j = (1 << n) - i
            if j in count:
                if i == j:
                    ans += count[i] * (count[i] - 1)
                else:
                    ans += count[i] * count[j]
    return (ans // 2) % m

deli = [1,7,3,6,5]
print(solve(deli))

इनपुट

[1,7,3,6,5]

आउटपुट

3