रिकर्सिव मल्टीप्लाई: आधा करके दोगुना करना (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.५: दो धनात्मक पूर्णांक बिना गुणा चिह्न के। छोटे गुणक के आधे पर रिकर्शन, आधे गुणनफल को दोगुना करो, विषम हो तो एक बार जोड़ो। सादा जावा।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

गुणा बार-बार जोड़ना है, पर क को खुद से ख बार जोड़ना तब धीमा पड़ता है जब दोनों संख्याएँ बड़ी हों। बेहतर तरीका है आधा और दोगुना: छोटे गुणक को आधा काटो, छोटा सवाल हल करो, फिर जवाब दोगुना करो (और अगर छोटा विषम था तो बड़े गुणक को एक बार और जोड़ो)। न *, न /। सिर्फ +, -, और चाहो तो बिट शिफ्ट।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू की क्लासिक रिकर्शन समस्याएँ, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रिकर्शन और डायनेमिक प्रोग्रामिंग, समस्या ८.५।

---

१. रोज़मर्रा की उपमा

एक पार्किंग सोचो जिसकी पंक्तियाँ और स्तंभ हों। दोनों पक्षों को गुणा किए बिना कुल जगहें चाहिए।

• एक-एक जगह गिनना काम करता है। पार्किंग बहुत बड़ी हो तो हमेशा लगता है।
• बेहतर: आधी पंक्तियाँ गिनो, फिर उस गिनती को दोगुना करो (आधी गिनती को खुद से जोड़ो)। तुमने आधे आकार की पार्किंग से दोगुना काम कर लिया।
• अगर पंक्तियों की संख्या विषम हो, आधा और आधा अभी भी एक पंक्ति कम है। आखिर में एक पूरी पंक्ति और जोड़ो।

संख्याओं में भी वही बात। ७ * ८ मतलब "सात आठ"। पहले ३ * ८ निकालो, दोगुना करो तो छह आठ, फिर ७ विषम होने से एक आठ और: ३*८ + ३*८ + ८।

आधा करने से काम सिकुड़ता है। दोगुना करने से गुणनफल फिर बनता है। विषम बचे हुए हिस्से के लिए बड़े गुणक का एक अतिरिक्त जोड़ चाहिए।

---

२. सादा समस्या कथन

इनपुट: दो धनात्मक पूर्णांक क और ख (कभी-कभी ० भी मान्य; उसे मुफ्त बेस केस मानो)।

आउटपुट: गुणनफल क * ख।

अभ्यास की पाबंदियाँ:

• * ऑपरेटर मत इस्तेमाल करो (और अगर मना हो तो दो से भाग के लिए / भी नहीं)।
• +, - और बिट शिफ्ट (<<, >>) चलेंगे।
• इन ऑपरेशनों की संख्या कम रखो (लॉग पैमाने का काम रैखिक से जीतता है)।

उदाहरण:

क	ख	गुणनफल	सोच
७	८	५६	७ का आधा ३; ३*८=२४; दोगुना ४८; +८ → ५६
८	७	५६	अदला-बदली से छोटा ७; वही रास्ता
५	५	२५	५ का आधा २; २*५=१०; दोगुना २०; +५ → २५
१	९९	९९	बेस केस: छोटा १
०	४०	०	बेस केस: छोटा ०
१६	३	४८	छोटा ३ विषम; आधा १; ३ दोगुना और +३

कोड से पहले साफ़ करो:

• सिर्फ धनात्मक, या शून्य और ऋणात्मक भी? यहाँ गैर-ऋणात्मक तक सीमित। ऋणात्मक चिह्न की किताबत उसी कोर के ऊपर है।
• ओवरफ़्लो? बड़े इनपुट पर इंट गुणनफल फट सकता है। लॉन्ग का ज़िक्र करो अगर मान २³¹-१ से ऊपर जा सकते हों।
• दोगुने के लिए << १ ठीक? हाँ। क + क भी ठीक, व्हाइटबोर्ड पर अक्सर साफ़।
• आधे के लिए >> १ ठीक? हाँ। अगर / बैन हो तो ज़ोर से कहो कि शिफ्ट इस्तेमाल कर रहे हो।

---

३. पहले सोचो

सीधा तरीका: छोटा जितनी बार जोड़ो

product = 0
repeat smaller times:
    product += bigger

सही है। समय ओ(छोटा)। छोटी संख्याओं पर ठीक। छोटा दस लाख हो तो कमज़ोर।

समझ: आधे का गुणनफल, फिर दोगुना

अगर छोटा सम हो:

smaller * bigger = 2 * ((smaller / 2) * bigger)

अगर छोटा विषम हो:

smaller * bigger = 2 * ((smaller / 2) * bigger) + bigger

क्योंकि विषम होने पर २ * फ़्लोर(छोटा/२) + १ = छोटा।

इसलिए छोटा >> १ पर एक रिकर्सिव कॉल काफी है, दो अलग आधे नहीं।

विषम पर दोनों आधे क्यों न चलाएँ

पहले स्केच में कभी-कभी ऐसा होता है:

side1 = minProduct(smaller >> 1, bigger)
side2 = minProduct(smaller - (smaller >> 1), bigger)  // when odd
return side1 + side2

जब छोटा विषम हो, दूसरा आधा पहले के बराबर नहीं। दो रिकर्सिव पेड़ खुलते हैं। काम दोहराता है। मेमो से ठीक हो सकता है, पर साफ़ सूत्र पहले ही दूसरा पेड़ काट देता है: आधे गुणनफल को दोगुना करो और बड़ा एक बार जोड़ो।

हमेशा छोटे गुणक पर रिकर्शन

३ * १०००००० सीधे लूप में गलत पक्ष चुनो तो दस लाख जोड़। अदला-बदली से छोटा = मिन(क, ख) रखो। गहराई ओ(लॉग मिन(क, ख)) रहती है।

ट्रेस: ७ × ८

minProduct(7, 8)
  half = 3
  halfProd = minProduct(3, 8)
    half = 1
    halfProd = minProduct(1, 8) = 8
    3 is odd → 8 + 8 + 8 = 24
  7 is odd → 24 + 24 + 8 = 56

तीन रिकर्सिव कदम। सीधे लूप में ८ सात बार जुड़ता।

ट्रेस: १६ × ३ (स्वैप के बाद: छोटा = ३)

minProduct(3, 16)
  halfProd = minProduct(1, 16) = 16
  3 is odd → 16 + 16 + 16 = 48

---

४. जावा समाधान

इंटरव्यू वाला पसंदीदा संस्करण: एक रिकर्सिव कॉल, आधे गुणनफल को खुद से जोड़कर दोगुना, विषम हो तो बड़ा जोड़ो।

/**
 * Multiply two non-negative ints without using * or /.
 * Recurses on half the smaller factor: O(log min(a, b)) adds.
 */
public static int minProduct(int a, int b) {
    int bigger = a < b ? b : a;
    int smaller = a < b ? a : b;
    return minProductHelper(smaller, bigger);
}

private static int minProductHelper(int smaller, int bigger) {
    if (smaller == 0) {
        return 0;
    }
    if (smaller == 1) {
        return bigger;
    }

    int half = smaller >> 1; // floor divide by 2
    int halfProd = minProductHelper(half, bigger);

    if ((smaller & 1) == 0) {
        // even: 2 * half * bigger
        return halfProd + halfProd;
    } else {
        // odd: 2 * floor(smaller/2) * bigger + bigger
        return halfProd + halfProd + bigger;
    }
}

वैकल्पिक: शिफ्ट से दोगुना

// same meaning as halfProd + halfProd when halfProd >= 0
return halfProd << 1;
// odd case:
return (halfProd << 1) + bigger;

शिफ्ट चतुर लगते हैं। तनाव में हाफ़प्रोड + हाफ़प्रोड समझाना आसान। दोनों ठीक अगर समझा सको।

कमज़ोर संस्करण जो लोग पहले लिखते हैं (जानो, फिर सुधारो)

// Linear: O(smaller) additions. Say it, then replace it.
private static int minProductNaive(int smaller, int bigger) {
    int sum = 0;
    for (int i = 0; i < smaller; i++) {
        sum += bigger;
    }
    return sum;
}

इंटरव्यूअर पहले ओ(स) सुनना पसंद करते हैं, फिर लॉग संस्करण।

वॉकथ्रू तालिका: ७ × ८

कॉल	आधा	आधा गुणनफल	सम/विषम	वापसी
हेल्पर(७, ८)	३	हेल्पर(३, ८) → २४	विषम	२४+२४+८ = ५६
हेल्पर(३, ८)	१	हेल्पर(१, ८) → ८	विषम	८+८+८ = २४
हेल्पर(१, ८)	-	-	बेस	८

न्यूनतम स्मोक टेस्ट

public static void main(String[] args) {
    System.out.println(minProduct(7, 8));   // 56
    System.out.println(minProduct(8, 7));   // 56
    System.out.println(minProduct(5, 5));   // 25
    System.out.println(minProduct(1, 99));  // 99
    System.out.println(minProduct(0, 40));  // 0
    System.out.println(minProduct(16, 3));  // 48
    System.out.println(minProduct(2, 2));   // 4
}

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
बड़ा को छोटा बार जोड़ना	ओ(स)	ओ(१)	सही आधार रेखा
विषम पर दो रिकर्सिव आधे	बिना मेमो लगभग ओ(स)	ओ(लॉग स) स्टैक	काम दोहराता है
दो आधे + मेमो ऐरे	ओ(स) भरना संभव	ओ(स) मेमो + स्टैक	बेहतर, पर सबसे अच्छी कहानी नहीं
एक आधा कॉल, दोगुना, विषम पर +बड़ा	ओ(लॉग स)	ओ(लॉग स) स्टैक	पसंदीदा

यहाँ स = मिन(क, ख)। पसंदीदा रास्ता हर कॉल पर स आधा करता है, इसलिए गहराई और जोड़ लॉग पैमाने पर हैं।

---

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

• शून्य → ० * क्ष = ०। बेस केस। अंतहीन जोड़ में मत फँसो।
• एक → तुरंत दूसरा गुणक लौटाओ।
• दोनों बराबर → चलता है; क == ख पर अदला-बदली कुछ नहीं बदलती।
• छोटा दो की घात → सम आधे के बाद सिर्फ दोगुना वाला रास्ता।
• बड़ा गुणनफल → इंट ओवरफ़्लो असली है। प्रोडक्शन में लॉन्ग कहो।
• ऋणात्मक → कथन अक्सर धनात्मक कहता है। पूछें तो चिह्न हटाओ, निरपेक्ष गुणा करो, चिह्न वापस लगाओ। फिर भी बिना *।

आम गलतियाँ:

१. छोटा गुणक पहले न रखना। जवाब सही, गहराई बड़े नंबर के पीछे चलती है। २. विषम पर बिना मेमो दो रिकर्सिव कॉल। काम करता है, धीमा, विश्लेषण मुश्किल। दोगुना + जोड़ बेहतर। ३. बिट्स की थीम पर छोटा % २। चलता है, पर (smaller & 1) == 0 "बिट्स चलेंगे" वाली बात से मेल खाता है। ४. / बैन होने पर भी / २। >> १ इस्तेमाल करो और बोलो। ५. ऋणात्मक हाफ़प्रोड पर << १। गैर-ऋणात्मक इनपुट पर समस्या नहीं; बाद में चिह्न आएँ तो + सुरक्षित। ६. ग्लोबल बदलना या सेलों की पूरी ग्रिड बनाना। ग्रिड सिखाने की तस्वीर है, ऐलोकेट करने वाली संरचना नहीं।

---

७. दोस्त को समझाने वाला सार

रिकर्सिव मल्टीप्लाई पूछता है: दो गैर-ऋणात्मक पूर्णांकों का गुणनफल बिना * या / के, जितने कम जोड़ हो सकें।

१. गुणा बार-बार जोड़ना है। स बार जोड़ना ईमानदार आधार है। २. हमेशा छोटे गुणक पर रिकर्शन करो ताकि काम मिन(क, ख) पर चले। ३. हाफ़प्रोड = गुणनफल(फ़्लोर(स/२), बड़ा) एक बार निकालो। ४. अगर स सम है, जवाब हाफ़प्रोड + हाफ़प्रोड। विषम हो तो बड़ा एक बार और जोड़ो। ५. बेस केस: ० → ०, १ → बड़ा। समय ओ(लॉग स), स्टैक ओ(लॉग स)।

अगर व्हाइटबोर्ड पर ७ × ८ को ५६ तक ले जा सको और समझा सको कि एक रिकर्सिव कॉल दो आधे गुणनफलों से क्यों जीतती है, तो समस्या ८.५ तुम्हारी है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: पावर सेट
• अगला: टावर्स ऑफ़ हनोई