FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/algorithms/cpp/additiveNumber/AdditiveNumber.cpp at master · wcoder0/leetcode · GitHub
wcoder0
leetcode
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
additiveNumber
/
AdditiveNumber.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
95 lines (81 loc) · 2.88 KB
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
additiveNumber
/
AdditiveNumber.cpp
Copy path
File metadata and controls
95 lines (81 loc) · 2.88 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
//
Source : https://leetcode.com/problems/additive-number/
//
Author : Hao Chen
//
Date : 2015-11-22
/*
**************************************************************************************
*
* Additive number is a positive integer whose digits can form additive sequence.
*
* A valid additive sequence should contain at least three numbers. Except for the
* first two numbers, each subsequent number in the sequence must be the sum of the
* preceding two.
*
* For example:
* "112358" is an additive number because the digits can form an additive sequence: 1,
* 1, 2, 3, 5, 8.
* 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
* "199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
* 1 + 99 = 100, 99 + 100 = 199
*
* Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2,
* 03 or 1, 02, 3 is invalid.
*
* Given a string represents an integer, write a function to determine if it's an
* additive number.
*
* Follow up:
* How would you handle overflow for very large input integers?
*
* Credits:Special thanks to @jeantimex for adding this problem and creating all test
* cases.
*
**************************************************************************************
*/
class
Solution
{
public:
bool
isAdditiveNumber
(string num) {
int
len = num.
size
();
for
(
int
i=
1
; i<len/
2
+
1
; i++) {
string n1 = num.
substr
(
0
, i);
if
( n1.
size
()>
1
&& n1[
0
] ==
'
0
'
)
break
;
for
(
int
j=i+
1
; j<len; j++) {
string n2 = num.
substr
(i, j-i);
if
( n2.
size
()>
1
&& n2[
0
] ==
'
0
'
)
break
;
string n3 = num.
substr
(j);
if
(
isAdditiveNumberHelper
(n1, n2, n3))
return
true
;
}
}
return
false
;
}
private:
bool
isAdditiveNumberHelper
(string& n1, string& n2, string& n3){
string add =
StringAdd
(n1, n2);
if
(add.
size
() > n3.
size
())
return
false
;
if
(add == n3 )
return
true
;
//
split the n3 to 2 parts, and keep going.
string cut = n3.
substr
(
0
, add.
size
());
if
(add == cut) {
string rest = n3.
substr
(add.
size
());
return
isAdditiveNumberHelper
(n2, add, rest);
}
return
false
;
}
string
StringAdd
(string n1, string n2) {
if
(n1.
size
() < n2.
size
()) {
string tmp = n1;
n1 = n2;
n2 = tmp;
}
int
carry=
0
;
string result;
for
(
int
i=n1.
size
()-
1
, j=n2.
size
()-
1
; i>=
0
; i--, j--) {
int
n = n1[i] -
'
0
'
+ carry;
if
( j >=
0
) {
n += n2[j] -
'
0
'
;
}
char
ch = n %
10
+
'
0
'
;
carry = n/
10
;
result = ch + result;
}
if
(carry>
0
) result = (
char
)(carry+
'
0
'
) + result;
return
result;
}
};
Back
|
FazBrowse Home
|
New Git URL