ধরুন আমাদের কাছে সংখ্যার একটি অ্যারে আছে; আমাদের একটি সংখ্যা B খুঁজে বের করতে হবে যেটি প্রদত্ত অ্যারের ঠিক একটি উপাদান ব্যতীত সকলের ভাজক। আমাদের মনে রাখতে হবে যে সমস্ত উপাদানের GCD 1 নয়।
সুতরাং, যদি ইনপুটটি {8, 16, 4, 24} এর মত হয়, তাহলে আউটপুট হবে 8 কারণ এটি 4 বাদে সকলের ভাজক।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=অ্যারের আকার
- যদি n 1 এর মত হয়, তাহলে
- রিটার্ন(অ্যারে[0] + 1)
- উপসর্গ :=n আকারের একটি অ্যারে, এবং 0 দিয়ে পূরণ করুন
- প্রত্যয় :=n আকারের একটি অ্যারে, এবং 0 দিয়ে পূরণ করুন
- প্রিফিক্স[0] :=অ্যারে[0]
- 1 থেকে n রেঞ্জের জন্য,
- করুন
- উপসর্গ[i] :=(অ্যারে[i] এবং উপসর্গ[i - 1]) এর gcd
- প্রত্যয়[n - 1] :=অ্যারে[n - 1]
- n - 2 থেকে -1 রেঞ্জে i এর জন্য, 1 দ্বারা হ্রাস করুন, করুন
- প্রত্যয়[i] :=(প্রত্যয়[i + 1] এবং অ্যারে[i]) এর gcd
- 0 থেকে n + 1 রেঞ্জের জন্য,
- করুন
- cur :=0
- যদি আমি 0 এর মত হয়, তাহলে
- cur :=প্রত্যয়[i + 1]
- অন্যথায় যখন i n - 1 এর মত হয়, তখন
- cur :=উপসর্গ[i - 1]
- অন্যথায়,
- cur :=gcd (উপসর্গ[i - 1] এবং প্রত্যয়[i + 1])
- যদি array[i] mod cur 0 এর মত না হয়, তাহলে
- রিটার্ন কার্
- রিটার্ন 0
উদাহরণ কোড
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from math import gcd def getDivisor(array): n = len(array) if (n == 1): return (array[0] + 1) prefix = [0] * n suffix = [0] * n prefix[0] = array[0] for i in range(1, n): prefix[i] = gcd(array[i], prefix[i - 1]) suffix[n - 1] = array[n - 1] for i in range(n - 2, -1, -1): suffix[i] = gcd(suffix[i + 1], array[i]) for i in range(0, n + 1): cur = 0 if (i == 0): cur = suffix[i + 1] elif (i == n - 1): cur = prefix[i - 1] else: cur = gcd(prefix[i - 1], suffix[i + 1]) if (array[i] % cur != 0): return cur return 0; array = [8, 16, 4, 24] print(getDivisor(array))
ইনপুট
[8, 16, 4, 24]
আউটপুট
8
