ধরুন আমাদের চারটি সংখ্যা n, a, b, এবং c আছে। a, b বা c দ্বারা বিভাজ্য সংখ্যার সাজানো ক্রমটির nম (0 সূচীকৃত) পদটি খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি 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)
- বামে :=1, ডানে :=10^9
- যখন বামে <=ডানে, কর
- মাঝে :=(বাম + ডান) / 2
- na :=মধ্য / a এর ভাগফল
- nb :=মধ্য / b এর ভাগফল
- nc :=মধ্য / c এর ভাগফল
- nab :=মধ্য / ab এর ভাগফল
- nbc :=মধ্য / bc এর ভাগফল
- nca :=মধ্য / ca এর ভাগফল
- nabc :=মধ্য / abc এর ভাগফল
- সংখ্যা :=na + nb + nc - nab - nbc - nca + nabc
- সংখ্যা হলে> n, তারপর
- ডান:=মধ্য - 1
- অন্যথায় যখন সংখ্যা
- বাম:=মধ্য + 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
