Skip to content

Instantly share code, notes, and snippets.

@james4388
Created June 1, 2020 19:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save james4388/528c7bb516bc02e007496a4ce21c1a07 to your computer and use it in GitHub Desktop.
Save james4388/528c7bb516bc02e007496a4ce21c1a07 to your computer and use it in GitHub Desktop.
Split array (not reorder item) in two equal sum. My stupid moment
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