Created
February 21, 2020 18:28
-
-
Save jmg-duarte/99d48b2b0066a279b333e8fae1050e93 to your computer and use it in GitHub Desktop.
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
def hash(v, size): | |
return abs(v) % size | |
def simple_zero_sum(arr): | |
_hash = lambda v: abs(v) % len(arr) | |
changes = 1 | |
while changes > 0: | |
changes = 0 | |
for idx, value in enumerate(arr): | |
curr_h = _hash(value) | |
target_h = _hash(arr[curr_h]) | |
# If the current index is equal to the current hashing number there is nothing to do | |
if idx == curr_h: | |
continue | |
# If the current value and the target sums to zero we found a pair | |
if value + arr[curr_h] == 0: | |
return True | |
# If the target number is in the position it should be, theres nothing we can do | |
if curr_h == target_h: | |
continue | |
# If the current value is equal to the target, we remove the out of order duplicate | |
if value == arr[curr_h]: | |
arr[idx] = 0 | |
changes += 1 | |
continue | |
# Swap the numbers out | |
v = arr[idx] | |
arr[idx] = arr[curr_h] | |
arr[curr_h] = v | |
changes += 1 | |
return False | |
def zero_sum(arr): | |
_hash = lambda v: hash(v, len(arr)) | |
it = 1 | |
changes = 1 | |
while changes > 0: | |
changes = 0 | |
it += 1 | |
for idx, value in enumerate(arr): | |
it += 1 | |
curr_h = _hash(value) | |
target_h = _hash(arr[curr_h]) | |
# If the current index is equal to the current hashing number there is nothing to do | |
if idx == curr_h: | |
continue | |
# If the current value and the target sums to zero we found a pair | |
if value + arr[curr_h] == 0: | |
return True | |
# If the target number is in the position it should be, theres nothing we can do | |
if curr_h == target_h: | |
continue | |
# If the current value is equal to the target, we remove the out of order duplicate | |
if value == arr[curr_h]: | |
arr[idx] = 0 | |
changes += 1 | |
continue | |
# Swap the numbers out | |
v = arr[idx] | |
arr[idx] = arr[curr_h] | |
arr[curr_h] = v | |
changes += 1 | |
return False | |
def naive(arr): | |
for e1 in arr: | |
for e2 in arr: | |
if e1 + e2 == 0: | |
return True | |
return False | |
def naive2(arr): | |
for idx, e1 in enumerate(arr): | |
for e2 in arr[idx + 1 :]: | |
if e1 + e2 == 0: | |
return True | |
return False | |
def hashing(arr): | |
aset = set() | |
for e in arr: | |
if -e in aset: | |
return True | |
aset.add(e) | |
return False | |
def sort_bin(arr): | |
arr.sort() | |
for e in arr: | |
if binsearch(arr, -e): | |
return True | |
return False | |
def sort_walk(arr): | |
arr.sort() | |
l = 0 | |
r = len(arr) - 1 | |
it = 0 | |
while l < r: | |
it += 1 | |
s = arr[l] + arr[r] | |
if s == 0: | |
print(it) | |
return True | |
elif s < 0: | |
l += 1 | |
else: | |
r -= 1 | |
print(it) | |
return False | |
test_arrays = [ | |
[4, -6, 3, -3, 4, 7], | |
[4, 4, 7, 3, -6, -3], | |
[4, -3, 7, -6, 3, 4], | |
[4, -6, 3, 4, -3, 7], | |
[-3, 7, 3, 4, 4, -6], | |
[3, -6, 4, 4, 7, -3], | |
[7, 4, 3, 4, -3, -6], | |
[4, 3, 4, 7, -6, -3], | |
[4, 7, -6, 3, -3, 4], | |
[3, 7, -6, -3, 4, 4], | |
[-6, 7, 4, 3, 4, -3], | |
[4, 7, -6, 4, 3, -3], | |
[-3, 4, 4, 3, 7, -6], | |
[-6, -3, 7, 4, 4, 3], | |
[3, -3, 4, 4, 7, -6], | |
[7, 4, -6, -3, 3, 4], | |
[4, 4, -3, 3, 7, -6], | |
[4, 4, 3, 7, -6, -3], | |
[-3, 3, 4, 7, 4, -6], | |
[7, 3, -3, 4, 4, -6], | |
[3, -6, 7, 4, -3, 4], | |
[4, 4, 3, -3, 7, -6], | |
[4, 7, 3, -3, -6, 4], | |
[3, -6, 4, 7, 4, -3], | |
[-6, 3, 4, 7, 4, -3], | |
[-3, 4, 4, 7, -6, 3], | |
[-6, -3, 4, 7, 3, 4], | |
[7, -3, 4, 3, -6, 4], | |
[-6, 4, -3, 3, 7, 4], | |
[4, -6, 3, 4, -3, 7], | |
[4, -3, 7, 3, 4, -6], | |
[-6, -3, 7, 4, 4, 3], | |
[7, 4, -6, -3, 4, 3], | |
[4, -6, 3, 7, -3, 4], | |
[-3, 4, 3, 7, -6, 4], | |
[-3, -6, 3, 4, 4, 7], | |
[3, -6, -3, 4, 4, 7], | |
[3, -6, 3, 4, 4, 7], | |
[4, 3, 3, 4, 7, -6], | |
[7, 4, 3, -6, 3, 4], | |
[3, 4, 3, 7, -6, 4], | |
[-6, 3, 3, 7, 4, 4], | |
[4, 7, 3, -6, 3, 4], | |
[-6, 4, 4, 7, 3, 3], | |
[4, -6, 4, 7, 3, 3], | |
[4, -6, 7, 3, 3, 4], | |
[3, 4, 7, 3, 4, -6], | |
[3, 7, -6, 4, 3, 4], | |
[4, 3, 4, -6, 3, 7], | |
[-6, 3, 4, 4, 7, 3], | |
[3, 7, 3, 4, -6, 4], | |
[-6, 4, 3, 7, 3, 4], | |
[4, 3, 3, -6, 4, 7], | |
[4, 3, 3, 7, -6, 4], | |
[7, 3, 4, 3, 4, -6], | |
[7, -6, 4, 4, 3, 3], | |
[4, 3, 3, -6, 7, 4], | |
[-6, 3, 3, 4, 4, 7], | |
[4, 3, -6, 4, 7, 3], | |
[3, 4, 4, 7, -6, 3], | |
[3, 4, 3, 4, -6, 7], | |
[7, -6, 3, 3, 4, 4], | |
[3, 4, 4, 3, 7, -6], | |
[4, 3, -6, 7, 3, 4], | |
[-6, 3, 4, 3, 4, 7], | |
[3, 4, 3, 7, 4, -6], | |
[3, 3, 4, 4, 7, -6], | |
[7, -6, 3, 4, 4, 3], | |
[4, 7, 3, 4, -6, 3], | |
[3, 7, 4, -6, 4, 3], | |
[3, 7, 4, -6, 3, 4], | |
[4, -6, 3, 4, 3, 7], | |
[3, 4, 4, 7, 3, -6], | |
[-6, 3, 7, 4, 4, 3], | |
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 28], | |
] | |
for arr in test_arrays: | |
print(simple_zero_sum(arr)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment