একটি অ্যারে A এবং একটি পূর্ণসংখ্যা K দেওয়া আছে। অ্যারে-র একটি সাবসিকোয়েন্স (subsequence) খুঁজে বের করতে হবে যেন সেই সাবসিকোয়েন্সের সব উপাদানের LCM (Least Common Multiple) ≤ K হয়। সাবসিকোয়েন্সটি দীর্ঘতম হতে হবে। LCM, দৈর্ঘ্য এবং ইনডেক্সগুলো ফেরত দিন।
উদাহরণ
ইনপুট: A = [3, 4, 5, 6], K = 20
আউটপুট: LCM = 12, Length = 3, Indexes = [0, 1, 3]
ব্যাখ্যা: সাবসিকোয়েন্স [3, 4, 6]-এর LCM = 12 ≤ 20।
সমাধানের পদ্ধতি
- প্রতিটি উপাদানের ফ্রিকোয়েন্সি গণনা করা হয়।
- ১ থেকে K পর্যন্ত প্রতিটি সংখ্যা x-র জন্য, কতগুলো অ্যারে উপাদান x-কে ভাগ করে সেটি গণনা করা হয় (এটি x-এর মাল্টিপল)।
- যে x-র জন্য এই কাউন্ট সবচেয়ে বেশি, সেই x হচ্ছে LCM এবং কাউন্টটি হচ্ছে দৈর্ঘ্য।
- সেই LCM-কে ভাগ করার সমস্ত উপাদানের ইনডেক্স প্রিন্ট করা হয়।
পাইথন কোড
from collections import defaultdict
def get_seq(A, k):
n = len(A)
my_dict = defaultdict(lambda: 0)
for i in range(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(f"LCM = {lcm}, Length = {size}")
print("Index values: ", end="")
for i in range(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
