memsql.py

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))