Python में विभिन्न सबसीक्वेंस GCDs की संख्या ज्ञात करें

धनात्मक पूर्णांकों की सरणी nums दी गई है। सभी गैर-खाली सबसीक्वेंस के GCDs में से अद्वितीय मानों की संख्या ज्ञात करें।

मुख्य अंतर्दृष्टि

एक मान x किसी सबसीक्वेंस का GCD हो सकता है यदि और केवल यदि nums में x के गुणज हैं जिनका GCD ठीक x है।

एल्गोरिदम: सीव-जैसा दृष्टिकोण

1. T = max(nums) + 1
2. nums को सेट में बदलें (O(1) लुकअप)
3. प्रत्येक x = 1 से T-1 के लिए:
   • x के सभी गुणज y जांचें जो nums में हैं
   • उनका GCD गणना करें
   • यदि GCD = x तो x एक वैध GCD है

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

from math import gcd

def count_different_subsequence_gcds(nums):
    T = max(nums) + 1
    num_set = set(nums)
    ans = 0
    
    for x in range(1, T):
        g = 0
        # x के सभी गुणज जांचें
        for y in range(x, T, x):
            if y in num_set:
                g = gcd(g, y)
                if g == x:  # जल्दी ब्रेक: GCD x तक पहुंच गया
                    break
        if g == x:
            ans += 1
    
    return ans

# परीक्षण
nums = [4, 6, 18]
print(count_different_subsequence_gcds(nums))  # 4

व्याख्या (nums = [4, 6, 18])

वैध GCDs: {2, 4, 6, 18} → उत्तर = 4

जटिलता

• समय: O(T log T) जहां T = max(nums)। हार्मोनिक श्रृंखला: Σ(T/x) = T log T
• स्थान: O(T) सेट के लिए

अनुकूलन

# उपस्थिति सरणी (सेट से तेज़)
present = [False] * T
for x in nums:
    present[x] = True

for x in range(1, T):
    g = 0
    for y in range(x, T, x):
        if present[y]:
            g = gcd(g, y)
            if g == x:
                break
    if g == x:
        ans += 1

मुख्य बिंदु

• प्रत्येक संभावित GCD मान x के लिए जांचें कि क्या यह प्राप्त करने योग्य है
• गुणजों पर पुनरावृति करके कुशलता से जांचें
• जल्दी ब्रेक जब GCD x तक पहुंच जाए
• यह दृष्टिकोण LeetCode "Number of Different Subsequences GCDs" समस्या का मानक समाधान है