मान लीजिए हमारे पास चार संख्याएं 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