मान लीजिए हमारे पास n विभिन्न संख्याओं का एक ऐरे A है और एक और धनात्मक पूर्णांक K है, हमें ऐरे में सबसे लंबा सब-सीक्वेंस ढूंढना है जिसका लघुत्तम समापवर्त्य (LCM) अधिकतम K हो। उसके बाद LCM और सब-सीक्वेंस की लंबाई लौटाएं, प्राप्त सब-सीक्वेंस के तत्वों के इंडेक्स (0 से शुरू) के बाद। अन्यथा, -1 लौटाएं।
तो, यदि इनपुट A = [3, 4, 5, 6], K = 20 जैसा है, तो आउटपुट होगा: LCM = 12, लंबाई = 3, इंडेक्स = [0,1,3]
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := A का आकार
my_dict := एक मैप
i को 0 से n तक के लिए, करें:
my_dict[A[i]] := my_dict[A[i]] + 1
count := आकार (k+1) का एक ऐरे 0 से भरा हुआ
my_dict में प्रत्येक कुंजी के लिए, करें:
यदि कुंजी <= k, तो:
i := 1
जब कुंजी * i <= k, करें:
count[कुंजी * i] := count[कुंजी * i] + my_dict[कुंजी]
i := i + 1
अन्यथा,
लूप से बाहर निकलें
lcm := 0, size := 0
i को 1 से k+1 तक के लिए, करें:
यदि count[i] > size, तो:
size := count[i]
lcm := i
यदि lcm, 0 के समान है, तो:
-1 लौटाएं
अन्यथा,
lcm और size प्रदर्शित करें
i को 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