मान लीजिए कि हमारे पास n अलग-अलग संख्याओं का एक सरणी A है और एक अन्य धनात्मक पूर्णांक K है, तो हमें उस सरणी में सबसे लंबा उप-अनुक्रम खोजना होगा, जिसमें अधिकतम K पर कम से कम सामान्य गुणक (LCM) हों। 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, तो
-
मैं :=1
-
जबकि कुंजी * i <=k, do
-
गिनती [कुंजी * i]:=गिनती [कुंजी * i] + my_dict [कुंजी]
-
मैं :=मैं + 1
-
-
-
अन्यथा,
-
लूप से बाहर आएं
-
-
-
एलसीएम:=0, आकार:=0
-
1 से k + 1 की श्रेणी में i के लिए, करें
-
अगर गिनती [i]> आकार, तो
-
आकार:=गिनती [i]
-
एलसीएम:=मैं
-
-
-
अगर एलसीएम 0 के समान है, तो
-
वापसी -1
-
-
अन्यथा,
-
एलसीएम और आकार प्रदर्शित करें
-
मेरे लिए 0 से n की सीमा में, करें
-
अगर lcm mod A[i] 0 के समान है, तो
-
मैं प्रदर्शित करता हूँ
-
-
-
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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