मान लीजिए हमें एक मैट्रिक्स दी गई है जिसमें n पंक्तियां और m कॉलम हैं। हमें मैट्रिक्स में क्रमागत एलिमेंट्स की सबसे बड़ी संख्या ढूंढनी है जहां एलिमेंट्स का GCD 1 से बड़ा है। क्रमागत एलिमेंट्स मैट्रिक्स में क्षैतिज या लंबवत रूप से हो सकते हैं।
इसलिए, यदि इनपुट है:
| 3 | 7 | 9 | 12 |
| 5 | 9 | 4 | 6 |
| 7 | 8 | 5 | 10 |
और m = 4, n = 3; तो आउटपुट 3 होगा।
दिए गए मैट्रिक्स का चौथा कॉलम 12, 6, 10 है। इस कॉलम के एलिमेंट्स का GCD 2 है। चूंकि तीन एलिमेंट्स हैं, उत्तर 3 है।
समाधान दृष्टिकोण
- 3D मैट्रिक्स बनाएं GCD मानों को संग्रहीत करने के लिए
- सभी संभावित पंक्ति रेंज के लिए पुनरावृति करें
- प्रत्येक कॉलम के लिए संचयी GCD की गणना करें
- लगातार कॉलम ट्रैक करें जहां GCD > 1 है
- अधिकतम लंबाई लौटाएं
उदाहरण कार्यान्वयन
from math import gcd
def solve(n, m, input_list):
mat = [[[0] * m for _ in range(n)] for _ in range(n)]
res = 0
for i in range(n):
for j in range(i, n):
gcd_temp = 0
x = 0
for k in range(m):
if i == j:
mat[i][j][k] = input_list[i][k]
else:
mat[i][j][k] = gcd(mat[i][j-1][k], input_list[j][k])
gcd_temp = gcd(gcd_temp, mat[i][j][k])
if gcd_temp > 1:
x += j - i + 1
else:
res = max(res, x)
if mat[i][j][k] > 1:
gcd_temp = mat[i][j][k]
x = j - i + 1
res = max(res, x)
return res
print(solve(3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]))इनपुट
3, 4, [[3, 7, 9, 12], [5, 9, 4, 6], [7, 8, 5, 10]]
आउटपुट
3
