-
Notifications
You must be signed in to change notification settings - Fork 1
/
67AddBinary.cs
69 lines (60 loc) · 1.7 KB
/
67AddBinary.cs
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _67
{
class Program
{
static void Main(string[] args)
{
string test = addBinary("1","111");
}
/*
* source code from blog:
* http://www.jiuzhang.com/solutions/add-binary/
*
* online judge:
* 294 / 294 test cases passed.
Status: Accepted
Runtime: 128 ms
*/
public static String addBinary(String a, String b)
{
int aLen = a.Length;
int bLen = b.Length;
if (aLen < bLen) // swap a and b
{
String tmp = a; // ensure that first argument a's length is longer than second argument string b.
a = b;
b = tmp;
}
int pa = a.Length - 1; // start from last one, decreasing order
int pb = b.Length - 1;
int carries = 0;
String rst = "";
while (pb >= 0)
{
int num1 = a[pa] - '0';
int num2 = b[pb] - '0';
int sum = num1 + num2 + carries;
rst = (sum % 2).ToString() + rst; // ?
carries = sum / 2;
pa--;
pb--;
}
while (pa >= 0)
{
int num = a[pa] - '0';
int sum = num + carries;
rst = (sum % 2).ToString() + rst;
carries = sum / 2;
pa--;
}
if (carries == 1)
rst = "1" + rst;
return rst;
}
}
}