স্ট্রিংস লেটকোড সলিউশনকে গুণ করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল ByteDance এক্সপিডিয়া ফেসবুক গুগল Houzz গণিত মাইক্রোসফট আকাশবাণী বর্গক্ষেত্র টুইটার উবার Zillow
ম্যাথ স্ট্রিং

স্ট্রিংস লেটকোড সমাধানটি মাল্টিপ্লাই স্ট্রিংগুলি আমাদেরকে দুটি স্ট্রিংগুলি ইনপুট হিসাবে প্রদত্ত দুটি গুণকে গুণতে বলেছে। আমাদের কলার ফাংশনে গুণনের এই ফলাফলটি মুদ্রণ করতে বা ফিরিয়ে আনতে হবে। সুতরাং এটি আরও আনুষ্ঠানিকভাবে দুটি স্ট্রিং দেওয়া, প্রদত্ত স্ট্রিংগুলির পণ্যটি সন্ধান করুন। এইগুলো স্ট্রিং অনেকগুলি সংখ্যা থাকতে পারে। সুতরাং একটিকে প্রদত্ত স্ট্রিংগুলিকে কেবল পূর্ণসংখ্যায় রূপান্তর করার চেষ্টা করা উচিত নয় এবং তারপরে সরল গুণটি ব্যবহার করা উচিত। আরও ভাল বোঝার জন্য কয়েকটি উদাহরণ একবার দেখুন।

উদাহরণ

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"

ব্যাখ্যা: এখন, এই উদাহরণে, আমাদের দুটি স্ট্রিং দেওয়া হয় যা একটি বৃহত স্ট্রিংকে আউটপুট হিসাবে গুণিত হয় যা একটি সংখ্যার ডেটা টাইপে সংরক্ষণ করা যায়নি। সুতরাং, আমাদের অ্যালগরিদম মোকাবেলায় সক্ষম হওয়া উচিত এমন কয়েকটিগুলির মধ্যে একটি উদাহরণ।

গুণিত স্ট্রিংস লেটকোড সমাধানের জন্য ব্রুট ফোর্স পদ্ধতির

স্ট্রিংস লেটকোড সলিউশনটি সমস্যাটি কেবলমাত্র দুটি প্রদত্ত স্ট্রিংকে গুণতে বলেছে। তো, আমরা কেন তা করি না? ভাল, এটি সফলভাবে প্রয়োগ করা কিছুটা জটিল। তবে, যদি আপনি মনে করেন আমরা কীভাবে দুটি সংখ্যাকে গুণ করব আমরা সহজেই এখানে একই কৌশলটি ব্যবহার করতে পারি।

সুতরাং, এই পদ্ধতির মধ্যে, আমরা প্রদত্ত স্ট্রিংগুলির মধ্যে একটি ডান থেকে বামে পেরিয়ে যাব। যখন আমরা কোনও সূচক বা কোনও চরিত্রের কাছে থাকি, আমরা এই বর্তমান অক্ষরটির সাথে অন্যান্য স্ট্রিংয়ের পুরোটি গুণ করি। একবার আমাদের গুণের সাথে সম্পন্ন হয়ে গেলে আমরা এর শেষে শূন্যগুলি যুক্ত করি। যোগ করতে হবে এমন শূন্যের সংখ্যা শেষ থেকে তার স্ট্রিংয়ের বর্তমান চরিত্রের অবস্থানের সমান - 1. একবার আমরা জিরো যুক্ত করার পরে, আমরা এই স্ট্রিংটিকে ফলাফলটিতে যুক্ত করব। সুতরাং, আমরা যেমন প্রথম স্ট্রিংয়ের ডান থেকে বাম দিকে অগ্রসর হয়েছি, ফলস্বরূপ স্ট্রিং উত্তরটি সঞ্চয় করে।

ব্রুট ফোর্স কোড

গুণিত স্ট্রিংস লেটকোড সমাধানের জন্য সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * এম), যেখানে এন প্রথম স্ট্রিংয়ের আকার এবং এম দ্বিতীয় স্ট্রিংয়ের আকার।

স্পেস জটিলতা ity

ও (এন + এম), যেহেতু আমরা ফলাফলটি একটি পৃথক স্ট্রিংয়ে সংরক্ষণ করেছি যার আকারের এন + এম থাকতে পারে। সুতরাং স্থান জটিলতা রৈখিক হয়।

মাল্টিপ্লাই স্ট্রিং লেটকোড সলিউশনের জন্য অনুকূলিত দৃষ্টিভঙ্গি

অপ্টিমাইজড অ্যাপ্রোচটি প্রথমে দেখার জন্য কিছুটা জটিল y অনুকূলিত পদ্ধতির উপরের ব্রুট ফোর্স পদ্ধতির মতো একই সময়ের জটিলতা রয়েছে তবে স্ট্রিংটিকে বিপরীত করার ওভারহেড ব্যয় এবং উত্তরের প্রতিটি মধ্যবর্তী ফলাফল স্ট্রিংয়ের যোগ সরিয়ে দেয়। অনুকূলিত পদ্ধতিতে, আমরা উভয় স্ট্রিংয়ের প্রতিটি অঙ্ককেই গুণ করি। সুতরাং, আমরা সূচকগুলির প্রতিটি জোড়া বিবেচনা করি, প্রথম স্ট্রিং থেকে একটি সূচক এবং অন্যটি দ্বিতীয় স্ট্রিং থেকে। ধারণাটি হ'ল সূচকগুলি যথাক্রমে প্রথম এবং দ্বিতীয় স্ট্রিংগুলিতে 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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * এম), জটিলতা হ'ল ব্রুট ফোর্স পদ্ধতির মতো হলেও, ওভারহেডের ব্যয়গুলি সরিয়ে ফেলা পারফরম্যান্সকে মারাত্মকভাবে উন্নত করে।

স্পেস জটিলতা ity

ও (এন + এম), কারণ ফলাফলযুক্ত স্ট্রিংয়ের আকারটি এন + এম, যেখানে এন প্রথম স্ট্রিংয়ের আকার এবং এম দ্বিতীয় স্ট্রিংয়ের আকার।