Python में N प्राकृतिक संख्याओं से उन जोड़ों की संख्या खोजने का प्रोग्राम जिनका योग k से विभाज्य हो

मान लीजिए हमारे पास एक संख्या n और दूसरा मान k है, मान लें हमारे पास पहले N प्राकृतिक संख्याओं के साथ एक ऐरे A है, हमें A से एलिमेंट्स A[i] और A[j] के जोड़ों की कुल संख्या ढूंढनी है, जैसे कि, i < j और उनका योग k से विभाज्य हो।

तो, यदि इनपुट n = 10, k = 4 है, तो आउटपुट 10 होगा क्योंकि 10 जोड़े हैं जिनका योग 4 से विभाज्य है। [(1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)]

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

• m := floor of (n / k), r := n mod k
• b := एक नया मैप
• i के लिए range 0 से k - 1 तक, करें
  • b[i] := m
• i के लिए range m*k+1 से n तक, करें
  • j := i mod k
  • b[j] := b[j] + 1
• c := 0
• i के लिए range 0 से k तक, करें
  • i1 := i
  • i2 :=(k - i) mod k
  • यदि i1, i2 के समान है, तो
    • c := c + b[i] *(b[i]-1)
  • अन्यथा,
    • c := c + b[i1] *(b[i2])
• floor of c/2 वापस करें

उदाहरण

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

def solve(n, k):     m = n // k     r = n % k     b = {} for i in range(k) : b[i] = m for i in range(m*k+1, n+1) : j = i % k b[j] = b[j] + 1 c = 0 for i in range(k) : i1 = i i2 = (k - i) % k if i1 == i2 : c = c + b[i] * (b[i]-1) else : c = c + b[i1] * (b[i2]) return c//2 n = 10 k = 4 print(solve(n, k))

इनपुट

4, 27 

आउटपुट

10