समस्या विवरण
एक "गुड मील" में ठीक दो अलग-अलग खाद्य पदार्थ होते हैं जिनकी स्वादिष्टता (deliciousness) का योग 2 की घात (power of two) होता है। दिए गए सरणी से ऐसे जोड़ों की संख्या गिनें।
उदाहरण 1
arr = [1, 3, 5, 7, 9] आउटपुट: 4 व्याख्या: जोड़े (1,3)=4, (1,7)=8, (3,5)=8, (7,9)=16 — सभी 2 की घात हैं।
उदाहरण 2
arr = [1,1,1,3,3,3,7] आउटपुट: 15 व्याख्या: (1,1) 3 तरीके, (1,3) 9 तरीके, (1,7) 3 तरीके।
समाधान दृष्टिकोण
- सरणी को सॉर्ट करें।
- प्रत्येक तत्व के लिए, संभावित 2 की घातों (1, 2, 4, 8, 16...) तक जांचें।
- हैश मैप (डिक्शनरी) से पहले देखे गए तत्वों की आवृत्ति ट्रैक करें।
- मॉड्यूलो 10^9+7 लें (बड़ी संख्याओं के लिए)।
पूर्ण कोड (लीटकोड शैली)
from collections import defaultdict
from typing import List
class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
MOD = 10**9 + 7
count = 0
freq = defaultdict(int)
for d in deliciousness:
# संभावित 2 की घात: 1, 2, 4, 8... 2*d तक
power = 1
while power <= 2 * d:
complement = power - d
count = (count + freq[complement]) % MOD
power <<= 1 # 2 से गुणा करें
freq[d] += 1
return count
# टेस्ट
sol = Solution()
print(sol.countPairs([1,3,5,7,9])) # 4
print(sol.countPairs([1,1,1,3,3,3,7])) # 15
आउटपुट
4 15
समय जटिलता: O(n log max_val), जहां max_val अधिकतम स्वादिष्टता मान है।
