Додадете бинарен раствор на лек кодови


Ниво на тешкотија Лесно
Често прашувано во Амазон Facebook Мајкрософт
Математика Стринг

Изјава за проблем

Со оглед на две бинарни жици a и b, мора да ги додадеме овие два жика и потоа да го вратиме резултатот како бинарна низа. Бинарна низа се низите што содржат само 0 и 1.

пример

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

Пристап

Додадете бинарен раствор на лек кодови

За додавање на две бинарни низи треба да извршиме додавање малку по малку. Како што знаеме собирањето се изведува од десниот крај движејќи се кон левите битови. Затоа, прво треба да ги свртиме дадените низи и потоа можеме да извршиме собирање на неговите битови почнувајќи од индексот 0.
За складирање на низа на додавање на битови можеме да создадеме низа променлива ОИЕ и додајте го збирот на два бита и носете на крајот од ОИЕ низа за секоја позиција на бит. Конечно ќе го вратиме ОИЕ низа за излез.

Алгоритам

  • Свртете ги дадените жици.
  • Создадете празна низа и a ги променлива. Иницијализирање ги со 0.
  • Повторете ја зададената низа за време на јамката и додадете малку од првата и втората низа заедно со носењето. Сега според вредноста на додатокот, додајте го добиениот бит на редицата и исто така ажурирајте ја ги за следниот бит.
  • Конечно имаме излезна низа, но таа е во обратен редослед затоа што за наша погодност извршивме додавање на обратна влезна низа. Завртете ја излезната низа и конечно вратете ја.

Имплементација

Програма C ++ за додавање бинарен раствор на код за код

#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

Анализа на комплексноста за додавање на бинарен раствор на леткод

Временска комплексност

О (максимум (Н, М)): Каде што N и M се должини на влезната низа. Додека ја минуваме низата линеарно во една јамка, сложеноста на времето ќе биде еднаква на максималната должина од двата влезни низа.

Комплексноста на просторот 

О (максимум (Н, М)): За складирање на резултатот во низа по додавање ни треба низа чија големина е еднаква на максимум од должината на влезните низи.