বাইনারি লেটকোড সমাধান যোগ করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক ফেসবুক মাইক্রোসফট
ম্যাথ স্ট্রিং

সমস্যা বিবৃতি

দুটি বাইনারি দেওয়া স্ট্রিং a এবং b, আমাদের এই দুটি স্ট্রিং যুক্ত করতে হবে এবং তারপরে বাইনারি স্ট্রিং হিসাবে ফলাফলটি ফিরিয়ে আনতে হবে। বাইনারি স্ট্রিংগুলি এমন স্ট্রিং যা কেবল 0 এবং 1 এস থাকে।

উদাহরণ

a = "11", b = "1"
"100"
a = "1010", b = "1011"
"10101"

অভিগমন

বাইনারি লেটকোড সমাধান যোগ করুন

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

অ্যালগরিদম

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

বাস্তবায়ন

বাইনারি লেটকোড সমাধানের জন্য সি ++ প্রোগ্রাম

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

string addBinary(string a, string b) 
{      
    int carry=0;
    string res="";

    reverse(a.begin(),a.end()); 
    reverse(b.begin(),b.end());

    int i=0,sum;
    while(i<a.size() || i<b.size())
    {
        sum= carry;

        if(i<a.size()) sum+= a[i]-'0';
        if(i<b.size()) sum+= b[i]-'0';

        if(sum==0) carry=0, res+='0';
        else if(sum==1)  carry=0, res+='1';
        else if(sum==2)carry=1, res+='0';
        else carry=1, res+='1';


        i++;
    }


    if(carry==1)  res+='1';

    reverse(res.begin(),res.end());
    return res;
        
}
int main()
{
  string a = "1010"; 
  string b = "1011";
  cout<<addBinary(a,b)<<endl;
}
10101

বাইনারি লেটকোড সমাধানের জন্য জাভা প্রোগ্রাম

import java.util.*;

class Rextester{
    
    public static String addBinary(String a, String b) 
    {      
        int carry=0;

        StringBuilder s1=new StringBuilder(a);
        StringBuilder s2=new StringBuilder(b);
        StringBuilder res=new StringBuilder();

        s1.reverse(); 
        s2.reverse();

        int i=0,sum;
        while(i<a.length() || i<b.length())
        {
            sum= carry;

            if(i<a.length()) sum+= s1.charAt(i)-'0';
            if(i<b.length()) sum+= s2.charAt(i)-'0';

            if(sum==0) 
            {
                 carry=0;
                 res.append('0');
            }
            if(sum==1) 
            {
                 carry=0;
                 res.append('1');
             }
            if(sum==2)
            {
                carry=1;
                res.append('0');
            }
           if(sum==3) 
            {
                carry=1;
                res.append('1');
            }

            i++;
        }
    
        if(carry==1)   res.append('1');

        res.reverse();
        return res.toString();
        
    }
    
  public static void main(String args[])
    {
        String a = "1010"; 
        String b = "1011";
        System.out.println(addBinary(a,b));
    }
}
10101

যুক্ত বাইনারি লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (সর্বোচ্চ (এন, এম)): যেখানে এন এবং এম ইনপুট স্ট্রিংয়ের দৈর্ঘ্য। যেহেতু আমরা উভয় স্ট্রিংকে একক লুপগুলিতে রৈখিকভাবে ট্র্যাভার্স করে যাচ্ছি, সময় জটিলতা দুটি ইনপুট স্ট্রিংগুলির মধ্যে সর্বোচ্চ দৈর্ঘ্যের সমান হবে।

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

ও (সর্বোচ্চ (এন, এম)): সংযোজনের পরে স্ট্রিংয়ে ফলাফল সংরক্ষণের জন্য আমাদের স্ট্রিং দরকার যার আকারটি ইনপুট স্ট্রিংয়ের সর্বাধিক দৈর্ঘ্যের সমান।