पायथन में सरणी में समान अंतराल वाले तत्वों का योग खोजने का प्रोग्राम

मान लीजिए, 'nums' नामक एक सरणी है जिसका आकार n है और जिसमें धनात्मक पूर्णांक हैं। हमारे पास 'queries' नामक एक और सरणी है जिसमें पूर्णांक युग्म (pi, qi) हैं। queries सरणी में प्रत्येक क्वेरी के लिए, उत्तर nums सरणी में उन तत्वों nums[j] का योग होगा जहां pi <= j < n और (j - pi), qi से विभाज्य है। हमें ऐसी सभी क्वेरीज के उत्तर लौटाने हैं, और यदि मान बड़ा है, तो उत्तर को 10^9 + 7 के मॉड्यूलो में लौटाएं।

उदाहरण के लिए, यदि इनपुट है nums = [2, 3, 4, 5, 6, 7, 8, 9, 10], queries = [(2, 5), (7, 3), (6, 4)], तो आउटपुट [13, 9, 8] होगा।

समाधान दृष्टिकोण

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

• A := nums

• Q := queries

• n := nums की लंबाई

• M := 10^9 + 7

• m := int(n^0.5) + 2 का पूर्णांक मान

• P := एक नई सूची जिसमें सूची A को m बार दोहराया गया हो

• i के लिए 1 से m तक लूप चलाएं

  • j के लिए n-1 से -1 तक घटाते हुए लूप चलाएं

    • यदि i+j < n, तो P[i][j] := (P[i][j] + P[i][i+j]) मॉड्यूलो M

• Q में प्रत्येक मान b, k के लिए

  • यदि k < m, तो P[k][b] से मान लौटाएं

  • अन्यथा, sum(A[b::k]) मॉड्यूलो M लौटाएं

उदाहरण

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

def solve(A, Q):
    n, M = len(A), 10**9+7
    m = int(n**0.5)+2
    P = [A[:] for _ in range(m)]
    for i in range(1,m):
        for j in range(n-1,-1,-1):
            if i+j < n:
                P[i][j] = (P[i][j]+P[i][i+j]) % M
    return [P[k][b] if k < m else sum(A[b::k]) % M for b, k in Q]

print(solve([2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]))

इनपुट

[2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]

आउटपुट

[13, 9, 8]