forked from mission-peace/interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlongestsamesumspan.py
More file actions
29 lines (23 loc) · 785 Bytes
/
longestsamesumspan.py
File metadata and controls
29 lines (23 loc) · 785 Bytes
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
# http://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/
# java code https://github.com/mission-peace/interview/blob/master/src/com/interview/array/LongestSameSumSpan.java
def longest_span(input1, input2):
if len(input1) != len(input2):
raise ValueError;
diff = {}
prefix1 = 0
prefix2 = 0
max_span = 0
diff[0] = -1
for i in range(len(input1)):
prefix1 += input1[i]
prefix2 += input2[i]
curr_diff = prefix1 - prefix2
if curr_diff in diff:
max_span = max(max_span, i - diff[curr_diff])
else:
diff[curr_diff] = i
return max_span
if __name__ == '__main__':
input1 = [1, 0, 0, 1, 1, 0]
input2 = [0, 1, 1, 0, 1, 1]
print(longest_span(input1, input2))