ধরুন আমাদের কাছে n ভিন্ন সংখ্যার একটি অ্যারে এবং আরেকটি ধনাত্মক পূর্ণসংখ্যা K আছে, আমাদের অ্যারের মধ্যে সবচেয়ে দীর্ঘতম সাব-সিকুয়েন্সটি খুঁজে বের করতে হবে যার মধ্যে Least Common Multiple (LCM) সর্বাধিক K থাকবে। LCM এবং সাবের দৈর্ঘ্য ফেরত দেওয়ার পরে -ক্রম, প্রাপ্ত উপ-অনুক্রমের উপাদানগুলির সূচী অনুসরণ করে (0 থেকে শুরু হয়)। অন্যথায়, -1 রিটার্ন করুন।
সুতরাং, যদি ইনপুট হয় A =[3, 4, 5, 6], K =20, তাহলে আউটপুট হবে LCM =12, দৈর্ঘ্য =3, সূচক =[0,1,3]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=A
এর আকার -
my_dict :=একটি মানচিত্র
-
0 থেকে n রেঞ্জের জন্য, করুন
-
my_dict[A[i]] :=my_dict[A[i]] + 1
-
-
গণনা :=আকারের একটি অ্যারে (k + 1) 0 দিয়ে পূরণ করুন
-
my_dict-এ প্রতিটি কী-এর জন্য করুন
-
যদি কী <=k, তারপর
-
i :=1
-
যখন কী * i <=k, do
-
গণনা [কী * i] :=গণনা[কী * i] + my_dict[কী]
-
i :=i + 1
-
-
-
অন্যথায়,
-
লুপ থেকে বেরিয়ে আসুন
-
-
-
lcm :=0, আকার :=0
-
1 থেকে k + 1 রেঞ্জের জন্য, করুন
-
যদি গণনা [i]> আকার, তাহলে
-
আকার :=গণনা[i]
-
lcm :=i
-
-
-
যদি lcm 0 এর সমান হয়, তাহলে
-
রিটার্ন -1
-
-
অন্যথায়,
-
প্রদর্শন lcm এবং আকার
-
0 থেকে n রেঞ্জের জন্য, করুন
-
যদি lcm mod A[i] 0 এর মত হয়, তাহলে
-
প্রদর্শন i
-
-
-
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from collections import defaultdict
def get_seq(A,k):
n = len(A)
my_dict = defaultdict(lambda:0)
for i in range(0, n):
my_dict[A[i]] += 1
count = [0] * (k + 1)
for key in my_dict:
if key <= k:
i = 1
while key * i <= k:
count[key * i] += my_dict[key]
i += 1
else:
break
lcm = 0
size = 0
for i in range(1, k + 1):
if count[i] > size:
size = count[i]
lcm = i
if lcm == 0:
print(-1)
else:
print("LCM = {0}, Length = {1}".format(lcm, size))
print("Index values: ", end = "")
for i in range(0, n):
if lcm % A[i] == 0:
print(i, end = " ")
k = 20
A = [3, 4, 5, 6]
get_seq(A,k) ইনপুট
[3, 4, 5, 6] , 20
আউটপুট
LCM = 12, Length = 3 Index values: 0 1 3
