सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

ग्रिड में सबसे बड़ा गुणनफल

ग्रिड में एक सीधी रेखा में लगी k संख्याओं का सबसे बड़ा गुणनफल खोजिए।

आप क्या सीखेंगे

  • Step जोड़ों की मदद से ग्रिड में चार दिशाओं में चलना
  • Run पढ़ने से पहले सीमाएँ जाँचना
  • अब तक का अधिकतम मान ट्रैक करना

समस्या

एक run सीधी रेखा में लगातार k खाने (cells) होते हैं: किसी पंक्ति में बाएँ से दाएँ, किसी स्तंभ में ऊपर से नीचे, या दोनों में से किसी भी विकर्ण पर। हर run की संख्याओं को आपस में गुणा कीजिए और वह run खोजिए जिसका गुणनफल सबसे बड़ा हो।

largest_product_in_grid(grid, k) लिखिए।

इनपुट

grid: संख्याओं का आयताकार ग्रिड; हर पंक्ति की लंबाई बराबर है।

k: run की लंबाई।

आउटपुट

लंबाई k वाले सभी runs में सबसे बड़ा गुणनफल लौटाइए। अगर किसी भी दिशा में लंबाई k का कोई run ग्रिड में न समाए तो 0 लौटाइए।

सीमाएँ

1 ≤ पंक्तियाँ, स्तंभ ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5

उदाहरण

उदाहरण 1
इनपुट:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 2

अपेक्षित आउटपुट:
expected = 72
इनपुट:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 2;

अपेक्षित आउटपुट:
long long expected = 72;
इनपुट:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 2;

अपेक्षित आउटपुट:
long expected = 72;

व्याख्या

सबसे अच्छा run नीचे की पंक्ति में 8 और 9 है: 8 × 9 = 72। विकर्ण 5, 9 से सिर्फ़ 45 मिलता है।

उदाहरण 2
इनपुट:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 3

अपेक्षित आउटपुट:
expected = 504
इनपुट:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 3;

अपेक्षित आउटपुट:
long long expected = 504;
इनपुट:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 3;

अपेक्षित आउटपुट:
long expected = 504;

व्याख्या

नीचे की पंक्ति से 7 × 8 × 9 = 504 मिलता है, जो दाएँ स्तंभ के 3 × 6 × 9 = 162 या किसी भी विकर्ण से बड़ा है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

चार दिशाएँ काफ़ी हैं: दाएँ, नीचे, नीचे-दाएँ और नीचे-बाएँ। बाकी दिशाएँ यही runs उलटे क्रम में दोहराती हैं।

संकेत 2

हर शुरुआती खाने से जाँचिए कि run का आख़िरी खाना अब भी ग्रिड के अंदर है।

संकेत 3

0 सिर्फ़ तब लौटाइए जब लंबाई k का कोई भी run न समाए।

अपेक्षित जटिलता

समय O(rows × cols × k), अतिरिक्त स्थान O(1)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।