Created
June 1, 2020 19:05
-
-
Save james4388/528c7bb516bc02e007496a4ce21c1a07 to your computer and use it in GitHub Desktop.
Split array (not reorder item) in two equal sum. My stupid moment
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from random import randint | |
def split(nums): | |
total = sum(nums) | |
if total % 2 != 0: | |
return False | |
half = total // 2 | |
sub_sum = 0 | |
for i, num in enumerate(nums): | |
sub_sum += num | |
if sub_sum == half: | |
return nums[:i+1], nums[i+1:] | |
return False | |
def split2(nums): | |
left = -1 | |
left_sum = 0 | |
right = len(nums) | |
right_sum = 0 | |
while left < right - 1: | |
if left_sum < right_sum: | |
left += 1 | |
left_sum += nums[left] | |
else: | |
right -= 1 | |
right_sum += nums[right] | |
if left_sum == right_sum: | |
return nums[:right], nums[right:] | |
return False | |
test_cases = [ | |
[1,2,3,4,10], | |
[10,1,2,3,4], | |
[1,2,3,4,5,5], | |
[5,5,1,2,3,4], | |
[1,2,3,3,2,1], | |
[1,2,3,4,3,2,1], | |
[1,2,3,4,4,3,2,1], | |
[1,2,3,4,5,4,3,2,1] | |
] | |
def gen_test_case(): | |
n = randint(5, 10) | |
return [randint(1, 100) for i in range(n)] | |
for i in range(1000): | |
test_cases.append(gen_test_case()) | |
for case in test_cases: | |
a = split(case) | |
b = split2(case) | |
if a != b: | |
print(a, b) | |
raise 'Failed' | |
else: | |
print(case, a) | |
# Benchmark | |
%timeit for case in test_cases: split(case) | |
%timeit for case in test_cases: split2(case) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment