समस्या
Take every contiguous window of span digits and multiply its digits. Return the largest product. Leading zeros are ordinary digits; a window containing zero has product zero. Do not reorder or skip digits.
Implement largest_adjacent_digit_product(digits, span).
Input
digits: The digit sequence, including any leading zeros.
span: The exact number of adjacent digits in a window.
Output
Return the greatest product over all windows of this width.
सीमाएँ
1 ≤ digit-string length ≤ 100,000. Characters are 0…9. 1 ≤ span ≤ min(18, length). All products fit signed 64-bit.
उदाहरण
इनपुट:
span = 2
digits = "23405"
अपेक्षित आउटपुट:
expected = 12इनपुट:
long long span = 2;
std::string digits = "23405";
अपेक्षित आउटपुट:
long long expected = 12;इनपुट:
long span = 2;
string digits = "23405";
अपेक्षित आउटपुट:
long expected = 12;व्याख्या
The windows 23, 34, 40, and 05 have products 6, 12, 0, and 0. The largest is 12.
इनपुट:
span = 3
digits = "102"
अपेक्षित आउटपुट:
expected = 0इनपुट:
long long span = 3;
std::string digits = "102";
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long span = 3;
string digits = "102";
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
There is only one width-three window. It contains zero, so 1 × 0 × 2 = 0.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Window के अंदर कोई zero हो तो product zero हो जाता है, इसलिए सिर्फ contiguous nonzero stretches maximum में योगदान दे सकते हैं।
संकेत 2
हर span को scratch से फिर से compute करने से बचने के लिए sliding window या digit runs के products track करो।
संकेत 3
Exact span requirement ध्यान से देखो: leading zeros digits गिने जाते हैं, और अगर span nonzero block से बड़ा हो जाए तो product zero है।
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।