Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में a, b, c से विभाज्य अनुक्रम का nth पद खोजने का प्रोग्राम


मान लीजिए हमारे पास चार संख्याएं n, a, b, और c हैं। हमें उन संख्याओं के सॉर्टेड अनुक्रम का nth (0-इंडेक्स्ड) पद ढूंढना है जो a, b या c से विभाज्य हों।

उदाहरण के लिए, यदि इनपुट n = 8, a = 3, b = 7, c = 9 है, तो आउटपुट 18 होगा, क्योंकि अनुक्रम के पहले 9 पद हैं [1, 3, 6, 7, 9, 12, 14, 15, 18]।

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

इस समस्या को हल करने के लिए हम बाइनरी सर्च और समावेश-बहिष्करण सिद्धांत का उपयोग करेंगे:

  • यदि a, b, c का न्यूनतम 1 के बराबर है, तो n लौटाएं
  • ab := lcm(a, b), bc := lcm(b, c), ca := lcm(a, c)
  • abc := lcm(ab, c)
  • left := 1, right := 10^9
  • जब तक left <= right:
    • mid := (left + right) // 2
    • na := mid // a, nb := mid // b, nc := mid // c
    • nab := mid // ab, nbc := mid // bc, nca := mid // ca
    • nabc := mid // abc
    • numterms := na + nb + nc - nab - nbc - nca + nabc
    • यदि numterms > n है, तो right := mid - 1
    • अन्यथा यदि numterms < n है, तो left := mid + 1
    • अन्यथा, mid - min(mid % a, mid % b, mid % c) लौटाएं
  • -1 लौटाएं

पायथन कार्यान्वयन

import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

class Solution:
    def solve(self, n, a, b, c):
        if min(a, b, c) == 1:
            return n
        ab, bc, ca = lcm(a, b), lcm(b, c), lcm(a, c)
        abc = lcm(ab, c)
        left, right = 1, 10 ** 9
        while left <= right:
            mid = (left + right) // 2
            na = mid // a
            nb = mid // b
            nc = mid // c
            nab = mid // ab
            nbc = mid // bc
            nca = mid // ca
            nabc = mid // abc
            numterms = na + nb + nc - nab - nbc - nca + nabc
            if numterms > n:
                right = mid - 1
            elif numterms < n:
                left = mid + 1
            else:
                return mid - min(mid % a, mid % b, mid % c)
        return -1

ob = Solution()
n = 8
a = 3
b = 7
c = 9
print(ob.solve(n, a, b, c))

इनपुट

8, 3, 7, 9

आउटपुट

18
  1. - पायथन में Nवीं फाइबोनैचि संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक संख्या n है, हमें nवीं फाइबोनैचि पद ढूंढना है। जैसा कि हम जानते हैं iवां फाइबोनैचि पद f(i) = f(i-1) + f(i-2), पहले दो पद 0, 1 हैं। उदाहरण के लिए, यदि इनपुट 15 है, तो आउटपुट 610 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे: first := 0, second := 1 i को 2 से n तक के

  1. - पायथन में दिए गए स्ट्रिंग अनुक्रम नियमों का पालन करके nth अनुक्रम खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो स्ट्रिंग्स s, t और एक अन्य धनात्मक संख्या n भी दी गई है, हमें अनुक्रम A का nवां पद लौटाना है जहां: A[0] = s A[1] = t जब n सम हो तो A[n] = A[n-1] + A[n-2], अन्यथा A[n] = A[n-2] + A[n-1]। उदाहरण के लिए, यदि s = a और t = b, तो अनुक्रम A होगा: [a, b, ba (a+b), bba (b+ba), bbaba

  1. - Python में दिए गए पुनरावृत्ति संबंध का nth पद ढूंढना

    मान लीजिए हमारे पास bn नामक संख्याओं का एक क्रम है, जिसे b1=1 और bn+1/bn=2n जैसे पुनरावृत्ति संबंध द्वारा दर्शाया गया है। हमें दिए गए n के लिए log2(bn) का मान ढूंढना है। तो, यदि इनपुट 6 की तरह है, तो आउटपुट 15 होगा क्योंकि log2(bn) = (n * (n - 1)) / 2 = (6*(6-1))/2 = 15। हम इस समस्या को इस संबंध को