forked from keshavsingh4522/hacktoberfest
-
Notifications
You must be signed in to change notification settings - Fork 0
/
AddBinary.cpp
127 lines (100 loc) · 2.87 KB
/
AddBinary.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
Problem:
"Add Binary" on LeetCode by AtrikGit6174
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
-- 1 <= a.length, b.length <= 104
-- a and b consist only of '0' or '1' characters.
-- Each string does not contain leading zeros except for the zero itself.
*/
#include <iostream>
#include <string>
#include <algorithm> //reverse()
using namespace std;
class Solution
{
public:
string addBinary(string a, string b)
{
if (a=="0")
return b;
if (b=="0")
return a;
int carry= 0;
//to avoid separate cases
string &big= (a.size()>=b.size()) ? a:b;
string &small= (a.size()<b.size()) ? a:b;
//reverse iterators
auto itbig= big.rbegin();
auto itsmall= small.rbegin();
int temp;
while (itsmall!=small.rend())
{
//exploting the fact that char is promoted to int
temp= (*itbig - '0') + (*itsmall - '0') + carry ;
if (temp>1)
carry= 1;
else
carry= 0;
switch (temp)
{
case 0:
case 2:
*itbig= '0';
break;
case 1:
case 3:
*itbig= '1';
break;
}
itsmall++;
itbig++;
}
if (carry)
{
while (itbig!=big.rend())
{
temp= carry + (*itbig - '0');
if (temp>1)
carry= 1;
else
carry= 0;
switch (temp)
{
case 0:
case 2:
*itbig= '0';
break;
case 1:
*itbig= '1';
break;
}
itbig++;
}
//overflow
if (carry and itbig==big.rend())
{
reverse(big.begin(), big.end());
big.push_back('1');
reverse(big.begin(), big.end());
}
}
return big;
}
};
int main ()
{
cout<<"Enter first binary string: ";
string a; cin>>a;
cout<<"\nEnter second binary string: ";
string b; cin>>b;
Solution *ob;
cout<<"\nSum= "<<ob->addBinary(a,b);
return 0;
}