સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશનને ગુણાકાર કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન ByteDance એક્સપેડિયા ફેસબુક Google હોઝ ગણિત માઈક્રોસોફ્ટ ઓરેકલ સ્ક્વેર Twitter ઉબેર ઝિલો
મઠ શબ્દમાળા

સમસ્યા મલ્ટીપ્લાય સ્ટ્રીંગ્સ લેટકોડ સોલ્યુશન અમને બે શબ્દમાળાઓને ગુણાકાર કરવાનું કહે છે જે અમને ઇનપુટ તરીકે આપવામાં આવે છે. અમારે કlerલર ફંક્શનમાં ગુણાકારના આ પરિણામને છાપવા અથવા પાછા આપવાની જરૂર છે. તેથી તેને વધુ formalપચારિક રૂપે બે શબ્દમાળાઓ મૂકવા માટે, આપેલ શબ્દમાળાઓનું ઉત્પાદન શોધો. આ શબ્દમાળાઓ ઘણા અંકો હોઈ શકે છે. તેથી કોઈએ આપેલ શબ્દમાળાઓને ફક્ત પૂર્ણાંકોમાં રૂપાંતરિત કરવાનો પ્રયાસ કરવો જોઈએ નહીં અને પછી સરળ ગુણાકારનો ઉપયોગ કરવો જોઈએ. ચાલો સારી સમજ માટે થોડા ઉદાહરણો પર એક નજર કરીએ.

ઉદાહરણો

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"

સમજૂતી: હવે, આ ઉદાહરણમાં, અમને બે શબ્દમાળાઓ આપવામાં આવી છે જે આઉટપુટ તરીકે મોટી શબ્દમાળા આપવા માટે ગુણાકાર કરવામાં આવે છે જે આંકડાકીય ડેટા પ્રકારમાં સાચવી શકાતી નથી. તેથી, આ ઉદાહરણ એ થોડા એવામાંનું એક છે કે જેનો ઉપયોગ અમારા અલ્ગોરિધમનો કરવા માટે સમર્થ હોવા જોઈએ.

મલ્ટીપ્લાય સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશન માટે બ્રુટ ફોર્સ અભિગમ

મલ્ટીપ્લાય સ્ટ્રીંગ્સ લેટકોડ સોલ્યુશનએ અમને આપેલા બે શબ્દમાળાઓને ગુણાકાર કરવાનું કહ્યું. તેથી, શા માટે આપણે ફક્ત તે જ કરતા નથી? ઠીક છે, તેને સફળતાપૂર્વક અમલમાં મૂકવું થોડું મુશ્કેલ છે. પરંતુ, જો તમને યાદ આવે કે અમે કેવી રીતે બે નંબરોનો ગુણાકાર કરતા હતા, અમે અહીં સમાન તકનીકનો ઉપયોગ સરળતાથી કરી શકીએ છીએ.

તેથી, આ અભિગમમાં, અમે આપેલ શબ્દમાળાઓમાંથી એક ઉપરથી જમણેથી ડાબેથી પસાર કરીશું. જ્યારે આપણે કોઈ અનુક્રમણિકા અથવા અક્ષર પર હોઈએ છીએ, ત્યારે આપણે આ વર્તમાન પાત્રથી બીજા શબ્દમાળાઓનો સંપૂર્ણ ગુણાકાર કરીએ છીએ. એકવાર આપણે આપણા ગુણાકાર સાથે થઈ ગયા પછી, અમે તેના અંતમાં શૂન્ય ઉમેરીશું. શૂન્યની સંખ્યા જે ઉમેરવાની છે તે તેના શબ્દમાળામાં વર્તમાન પાત્રની સ્થિતિને અંતથી સમકક્ષ છે. તેથી, જેમ આપણે પહેલા શબ્દમાળાની જમણીથી ડાબી બાજુએ ગયા છીએ, પરિણામે શબ્દમાળા જવાબ સંગ્રહ કરે છે.

બ્રુટ ફોર્સ કોડ

મલ્ટીપ્લાય સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશન માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * એમ), જ્યાં એન એ પ્રથમ શબ્દમાળા નું કદ છે અને એમ બીજા શબ્દમાળા નું કદ છે.

અવકાશ જટિલતા

ઓ (એન + એમ), કારણ કે અમે પરિણામને અલગ શબ્દમાળામાં સંગ્રહિત કર્યું છે જેમાં N + M નું કદ હોઈ શકે છે. આમ જગ્યા જટિલતા રેખીય છે.

મલ્ટીપ્લાય સ્ટ્રીંગ્સ લેટકોડ સોલ્યુશન માટે .પ્ટિમાઇઝ અભિગમ

Goપ્ટિમાઇઝ અભિગમ પ્રથમ જવામાં અવલોકન કરવા માટે થોડી મુશ્કેલ છે. Izedપ્ટિમાઇઝ એપ્રોચ પણ ઉપરોક્ત બ્રુટ ફોર્સ એપ્રોચની જેમ જ સમયની જટિલતા ધરાવે છે પરંતુ શબ્દમાળાને વિરુદ્ધ કરવાના ઓવરહેડ ખર્ચને દૂર કરે છે અને દરેક મધ્યવર્તી પરિણામી શબ્દમાળાને જવાબમાં ઉમેરવામાં આવે છે. Optimપ્ટિમાઇઝ અભિગમમાં, અમે બંને શબ્દમાળાઓના દરેક અંકોને ગુણાકાર કરીએ છીએ. આ રીતે, અમે સૂચકાંકોની દરેક જોડીને ધ્યાનમાં લઈએ છીએ, પ્રથમ તારથી એક અનુક્રમણિકા અને બીજું બીજા શબ્દમાળાથી. વિચાર એ છે કે જો સૂચકાંકો અનુક્રમે પ્રથમ અને બીજા શબ્દમાળા i, j હોય, તો તેઓ પરિણામી શબ્દમાળામાં i + j, i + j + 1 સૂચકાંકો મેળવે છે. તેથી આ તથ્યનો ઉપયોગ કરીને, અમે ઓવરહેડને દૂર કરી શકીએ છીએ જે મધ્યવર્તી તાર ઉમેરવામાં, ઝીરો ઉમેરીને, મધ્યવર્તી તારને વિરુદ્ધ કરવામાં જે ખોટાઇ રહ્યું હતું તે દૂર થઈ શકે છે જે સોલ્યુશનને તીવ્ર ઝડપી બનાવે છે. નીચેની તસવીર જોવી તે વધુ સારી રીતે સમજશે.

સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશનને ગુણાકાર કરો

Opપ્ટિમાઇઝ કોડ

મલ્ટીપ્લાય સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશન માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * એમ), જટિલતા જડ બળ પદ્ધતિ જેવી જ હોવા છતાં, ઓવરહેડ ખર્ચ દૂર કરવાથી કામગીરીમાં ધરખમ સુધારો થાય છે.

અવકાશ જટિલતા

ઓ (એન + એમ), કારણ કે પરિણામી શબ્દમાળાનું કદ એન + એમ છે, જ્યાં એન પ્રથમ શબ્દમાળાઓનું કદ છે, અને એમ બીજા શબ્દમાળાઓનું કદ છે.