स्ट्रिंग्स लीटकोड सोल्यूशन गुणाकार करा  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सफरचंद बाइट डान्स यामध्ये फेसबुक Google होज गणिते मायक्रोसॉफ्ट ओरॅकल स्क्वेअर ट्विटर उबेर झिलो
अल्गोरिदम कोडिंग मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions गणित अक्षरमाळा

स्ट्रीप्स लीटकोड सोल्यूशन प्रॉब्लेम, आम्हाला इनपुट म्हणून दिलेली दोन स्ट्रिंग गुणाकार करण्यास सांगते. आम्हाला कॉलर फंक्शनमध्ये गुणाकार करण्याचा हा परिणाम प्रिंट करणे किंवा परत करणे आवश्यक आहे. तर त्यास अधिक औपचारिकरित्या दोन तार दिल्यास दिलेल्या तारांचे उत्पादन शोधा. या स्ट्रिंग्स बरेच अंक असू शकतात. म्हणून एखाद्याने दिलेली स्ट्रिंग केवळ पूर्णामध्ये रूपांतरित करण्याचा प्रयत्न करू नये आणि नंतर साध्या गुणाकाराचा वापर करू नये. चांगल्या प्रकारे समजून घेण्यासाठी काही उदाहरणे पहा.

उदाहरणे  

First String: "2"
Second String: "3"
Resultant String: "6"

स्पष्टीकरणः दोन्ही तारांना एकच अंक आहेत. आउटपुट 6 असायला हवे हे तपासू शकतो आणि तेच आहे.

First String: "123"
Second String: "456"
Resultant String: "56088"

स्पष्टीकरणः या उदाहरणात देखील, आपल्याला दोन तार प्रदान केल्या आहेत, ज्या नंतर “56088” देण्यासाठी गुणाकार केल्या जातात.

First String: "123"
Second String: "0"
Resultant String: "0"

स्पष्टीकरणः येथे आम्ही “000” किंवा “00” छापले नाही. जर निकाल 0 असेल तर आपल्याला एकच “0” प्रिंट करणे आवश्यक आहे.

First String: "123456789"
Second String: "987654321123456789987"
Resultant String: "121932631127876847872042371743"

स्पष्टीकरणः आता या उदाहरणात, आपल्याला दोन स्ट्रिंग्स दिलेली आहेत जे मोठ्या स्ट्रिंगस देण्यासाठी आउटपुट म्हणून गुणाकार आहेत जे आकडेवारीच्या प्रकारात जतन करणे शक्य नव्हते. तर, हे उदाहरण आमच्या अल्गोरिदमला सामोरे जायला हवे यापैकी काहींपैकी एक आहे.

हे सुद्धा पहा
आयत लीटकोड सोल्यूशन बनवा

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनसाठी ब्रूट फोर्स अ‍ॅप्रोच  

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनने समस्या आम्हाला दिलेली दोन तारांची गुणाकार करण्यास सांगितले. तर मग आपण ते का करत नाही? हे यशस्वीरित्या अंमलात आणणे थोडे अवघड आहे. परंतु, जर आपल्याला आठवत असेल की आम्ही दोन आकड्यांची संख्या कशी वाढवितो तर आम्ही तेच तंत्र सहजपणे वापरू शकतो.

तर या पध्दतीमध्ये आपण दिलेल्या तारांपैकी उजवीकडून डावीकडे ओलांडू. जेव्हा आपण अनुक्रमणिका किंवा एखाद्या वर्णात असतो तेव्हा आम्ही या वर्तमान वर्णासह संपूर्ण इतर स्ट्रिंग गुणाकार करतो. एकदा आम्ही आमच्या गुणाकारानंतर, आम्ही त्याच्या शेवटी शून्य जोडू. जोडल्या जाणा z्या शून्यांची संख्या शेवटच्या स्ट्रिंगमधील सध्याच्या अक्षराच्या स्थानाइतकीच असते - १. एकदा आपण शून्य जोडण्याचे काम पूर्ण केल्यावर आपण ही स्ट्रिंग निकालामध्ये जोडतो. म्हणून जसे आपण पहिल्या स्ट्रिंगच्या डावीकडून डावीकडे सरकलो आहोत, परिणामी स्ट्रिंग उत्तर साठवते.

ब्रूट फोर्स कोड

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनसाठी सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

inline string add_zero(int n){
    string res = "";
    while(n-- > 0)res += "0";
    return res;
}

string add_string(string& a, string& b){
    if(a.size()>b.size())swap(a,b);
    int a_len = a.size(), b_len = b.size();
    string res = "";
    int sum = 0, carry = 0;
    for(int i=0;i<b_len;i++){
        int a_idx = a_len-1-i, b_idx = b_len-1-i;
        sum = carry + (a_idx>=0 ? (a[a_idx]-'0') : 0) + (b[b_idx]-'0');
        carry = sum/10; sum %= 10;
        res += to_string(sum);
    }
    if(carry>0)
        res += to_string(carry);
    reverse(res.begin(), res.end());
    return res;
}

string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0")
        return "0";
    string res = "";
    if(num1.size()>num2.size())swap(num1, num2);
    int num1_len = num1.size(), num2_len = num2.size();
    for(int i=num1_len-1;i>=0;i--){
        int multiplier = num1[i]-'0';
        int sum = 0, carry = 0;
        string cur_res = "";
        for(int j=num2_len-1;j>=0;j--){
            sum = carry + (num2[j]-'0')*multiplier;
            carry = sum/10; sum %= 10;
            cur_res += to_string(sum);
        }
        if(carry>0)
            cur_res += to_string(carry);
        reverse(cur_res.begin(), cur_res.end());
        cur_res += add_zero(num1_len-i-1);
        res = add_string(res, cur_res);
    }
    return res;
}

int main(){
    string num1 = "123";
    string num2 = "456";
    cout<<multiply(num1, num2);
}
56088

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनसाठी जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
     private static String add_zero(int n){
        String res = "";
        while(n-- > 0)res += "0";
        return res;
    }
    
    private static String add_string(String a, String b){
        if(a.length()>b.length()){
            String tmp = a;
            a = b;
            b = tmp;
        }
        int a_len = a.length(), b_len = b.length();
        String res = "";
        int sum = 0, carry = 0;
        for(int i=0;i<b_len;i++){
            int a_idx = a_len-1-i, b_idx = b_len-1-i;
            sum = carry + (a_idx>=0 ? (a.charAt(a_idx)-'0') : 0) + (b.charAt(b_idx)-'0');
            carry = sum/10; sum %= 10;
            res += Integer.toString(sum);
        }
        if(carry>0)
            res += Integer.toString(carry);
        StringBuilder sb = new StringBuilder(res);
        sb.reverse();
        return sb.toString();
    }
    
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        String res = "";
        if(num1.length()>num2.length()){
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        int num1_len = num1.length(), num2_len = num2.length();
        for(int i=num1_len-1;i>=0;i--){
            int multiplier = num1.charAt(i)-'0';
            int sum = 0, carry = 0;
            String cur_res = "";
            for(int j=num2_len-1;j>=0;j--){
                sum = carry + (num2.charAt(j)-'0')*multiplier;
                carry = sum/10; sum %= 10;
                cur_res += Integer.toString(sum);
            }
            if(carry>0)
                cur_res += Integer.toString(carry);
            StringBuilder sb = new StringBuilder(cur_res);
            sb.reverse();
            sb.append(add_zero(num1_len-i-1));
            res = add_string(res, sb.toString());
        }
        return res;
    }
    
    public static void main(String[] args){
    	String num1 = "123";
    	String num2 = "456";
    	System.out.println(multiply(num1, num2));
    }
}
56088

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * एम), जेथे एन पहिल्या स्ट्रिंगचा आकार आहे आणि एम दुसर्‍या स्ट्रिंगचा आकार आहे.

हे सुद्धा पहा
बायनरी ट्रीमध्ये जास्तीत जास्त पातळीची बेरीज शोधा

स्पेस कॉम्प्लेक्सिटी

ओ (एन + एम), आम्ही परिणाम वेगळ्या स्ट्रिंगमध्ये संग्रहित केला आहे ज्याचा आकार एन + एम असू शकतो. अशा प्रकारे अवकाशातील जटिलता रेखीय असते.

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनसाठी ऑप्टिमाइझ केलेला दृष्टीकोन  

ऑप्टिमाइझ केलेला दृष्टिकोन पहिल्यांदा पाहणे थोडे अवघड आहे. ऑप्टिमाइझ केलेला दृष्टिकोन देखील वरील ब्रूट फोर्स अप्रोच प्रमाणेच वेळची जटिलता आहे परंतु स्ट्रिंगला उलट्या करण्याच्या ओव्हरहेड खर्च आणि प्रत्येक इंटरमीडिएट परिणामी स्ट्रिंगची उत्तरेसह जोडते. ऑप्टिमाइझ दृष्टिकोनात आम्ही दोन्ही तारांचे प्रत्येक अंक गुणाकार करतो. अशा प्रकारे, आम्ही निर्देशांकांच्या प्रत्येक जोडीचा विचार करतो, पहिल्या स्ट्रिंगमधून एक इंडेक्स आणि दुसर्‍या स्ट्रिंगमधून. कल्पना अशी आहे की जर निर्देशांक पहिल्या आणि दुसर्‍या क्रमांकाच्या अनुक्रमे i, j असतील तर ते परिणामी स्ट्रिंगमध्ये i + j, i + j + 1 निर्देशांक मिळवतात. तर या वस्तुस्थितीचा वापर करून, आम्ही ओव्हरहेड काढून टाकू शकतो जे इंटरमीडिएट स्ट्रिंग्स जोडणे, शून्य जोडणे, इंटरमिजिएट स्ट्रिंग्स रिव्हर्सिंगमुळे द्रावणात तीव्र वाढ करते. खाली दिलेली प्रतिमा पहात असल्यास हे समजणे अधिक चांगले होईल.

स्ट्रिंग्स लीटकोड सोल्यूशन गुणाकार करापिन

ऑप्टिमाइझ केलेला कोड

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनसाठी सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0")
            return "0";
        if(num1.size()>num2.size())swap(num1, num2);
        int num1_len = num1.size(), num2_len = num2.size();
        int res[num1_len+num2_len];memset(res, 0, sizeof res);
        for(int i=num1_len-1;i>=0;i--){
            for(int j=num2_len-1;j>=0;j--){
                int p1 = i+j, p2 = p1+1;
                int sum = (num1[i]-'0')*(num2[j]-'0') + res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        string output = ""; int idx = -1;
        for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
            idx = i;
        for(int i=idx+1;i<num1_len+num2_len;i++)
            output += to_string(res[i]);
        return output;
    }

int main(){
    string num1 = "123";
    string num2 = "456";
    cout<<multiply(num1, num2);
}
56088

मल्टीप्ली स्ट्रिंग्स लेटकोड सोल्यूशनसाठी जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))
            return "0";
        if(num1.length()>num2.length()){
            String tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        int num1_len = num1.length(), num2_len = num2.length();
        int res[] = new int[num1_len+num2_len];
        Arrays.fill(res, 0);
        for(int i=num1_len-1;i>=0;i--){
            for(int j=num2_len-1;j>=0;j--){
                int p1 = i+j, p2 = p1+1;
                int sum = (num1.charAt(i)-'0')*(num2.charAt(j)-'0') + res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        String output = ""; int idx = -1;
        for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
            idx = i;
        for(int i=idx+1;i<num1_len+num2_len;i++)
            output += Integer.toString(res[i]);
        return output;
    }
    
    public static void main(String[] args){
    	String num1 = "123";
    	String num2 = "456";
    	System.out.println(multiply(num1, num2));
    }
}
56088

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * एम), जरी जटिलता जबरदस्तीच्या पध्दतीप्रमाणे असली तरीही, ओव्हरहेड खर्च काढून टाकल्याने कार्यक्षमतेत मोठ्या प्रमाणात सुधारणा होते.

हे सुद्धा पहा
सतत अतिरिक्त जागेचा वापर करून बीएसटी मधील सर्वात मोठा घटक के

स्पेस कॉम्प्लेक्सिटी

ओ (एन + एम), कारण परिणामी स्ट्रिंगचा आकार एन + एम आहे, जेथे एन पहिल्या स्ट्रिंगचा आकार आहे आणि एम दुसर्‍या स्ट्रिंगचा आकार आहे.