Is there algorithm for 3SUM which have complexity O(n) or O($n^{3/2}$) for randomly chosen input with bit length of maximum number approximately equal to count of input numbers?



Is there fast algorithm for 3SUM?
Yes, here it is (code in Python):



```
from collections import Counter
from math import ceil, log
from random import randint


def rnd(n):
    return randint(0, n - 1)

def get_bit_len(n):
    if n == 0:
        res = 1
    else:
        res = int(ceil(log(n + 1) / log(2)))
    return res

def rev_bits_to_int(bits):
    res = 0
    for bit in reversed(bits):
        res = (res << 1) | bit
    return res

def to_bin_list(n, len_ = None):
    if len_ is None:
        len_ = get_bit_len(n)
    bin_str = bin(n)[2:]
    zeros = [0 for i in range(len_ - len(bin_str))]
    digits = [int(bin_str[i]) for i in range(len(bin_str))]
    return zeros + digits

def to_rev_bits(n, len_ = None):
    res = to_bin_list(n, len_)
    res.reverse()
    return res

def to_bit_ar2(l, bit_len = None):
    n = len(l)
    if bit_len is None:
        bit_len = get_bit_len(max(l))
    l1 = l[:]
    res = [[0 for bit_pos in range(bit_len)] for num_pos in range(n)]
    for num_pos in range(n):
        for bit_pos in range(bit_len):
            res[num_pos][bit_pos] = l1[num_pos] % 2
            l1[num_pos] //= 2
    return res

def get_is_sum_3(numbers, target):
    numbers = [3 * elt - target for elt in numbers]
    counts = Counter(numbers)
    num_counts = sorted(counts.items())
    if counts[0] >= 3:
        return 1
    for i, (first, first_count) in enumerate(num_counts):
        if first_count >= 2 and first < 0 and -(first * 2) in counts:
            return 1
        for j in range(i + 1, len(num_counts)):
            second, second_count = num_counts[j]
            if second_count >= 2 and -first == 2 * second:
                return 1
            third = -(first + second)
            if third > second and third in counts:
                return 1
    return 0

def rec_to_compressed_bits(bit_ar2, bit_num, start_num, limit_num, tree):
    tree.extend([[], [], start_num, -1, limit_num])
    for num_num in range(start_num, limit_num):
        if bit_ar2[num_num][bit_num] == 1:
            tree[3] = num_num
            break
    if tree[3] == -1:
        tree[3] = limit_num
    if bit_num < len(bit_ar2[0]) - 1:
        if tree[3] - tree[2] > 0:
            rec_to_compressed_bits(bit_ar2, bit_num + 1, tree[2], tree[3], tree[0])
        if tree[4] - tree[3] > 0:
            rec_to_compressed_bits(bit_ar2, bit_num + 1, tree[3], tree[4], tree[1])

def to_compressed_bits(bit_ar2):
    bit_ar2.sort()
    res = []
    bit_num = 0
    start_num = 0
    limit_num = len(bit_ar2)
    rec_to_compressed_bits(bit_ar2, bit_num, start_num, limit_num, res)
    return res

def rec_explore_sum_3_trees(bit_len, target, target_bits, prev_bit_num, prev_branch_bits, prev_branch_sum, prev_compressed_bits_record, prev_div_record, stat_box):
    bit_num = prev_bit_num + 1 #
    if prev_branch_sum == target and bit_num == bit_len - 1: #
        return 1
    if prev_branch_bits[bit_num] == target_bits[bit_num]:
        if len(prev_div_record[0]) == 3:
            div_records = [((0,), (1, 1), 2), ((0, 0, 0), 0)]
        elif len(prev_div_record[0]) == 2:
            div_records = [((0,), (1,), (1,), 2), ((0, 0), (0,), 0), ((1, 1), (0,), 2)]
        elif len(prev_div_record[1]) == 2:
            div_records = [((1,), (0,), (1,), 2), ((0,), (0, 0), 0), ((0,), (1, 1), 2)]
        elif len(prev_div_record[2]) == 1:
            div_records = [((0,), (0,), (0,), 0), ((0,), (1,), (1,), 2), ((1,), (0,), (1,), 2), ((1,), (1,), (0,), 2)]
    else:
        if len(prev_div_record[0]) == 3:
            div_records = [((0, 0), (1,), 1), ((1, 1, 1), 3)]
        elif len(prev_div_record[0]) == 2:
            div_records = [((0,), (1,), (0,), 1), ((1, 1), (1,), 3), ((0, 0), (1,), 1)]
        elif len(prev_div_record[1]) == 2:
            div_records = [((0,), (0,), (1,), 1), ((1,), (1, 1), 3), ((1,), (0, 0), 1)]
        elif len(prev_div_record[2]) == 1:
            div_records = [((1,), (1,), (1,), 3), ((0,), (0,), (1,), 1), ((0,), (1,), (0,), 1), ((1,), (0,), (0,), 1)]
    for div_record in div_records:
        stat_box[0] += 1 # complexity counter
        branch_sum = rev_bits_to_int(prev_branch_bits) + div_record[-1] * 2**bit_num # can be faster
        if branch_sum > target or branch_sum != target and bit_num == bit_len - 1:
            continue
        else:
            branch_bits = to_rev_bits(branch_sum, len(target_bits)) # can be faster
            cur_bit_count = 0
            prev_div_pos = 0
            div_pos = 0
            is_found = 1
            compressed_bits_record = []
            while cur_bit_count < 3:
                bit = div_record[div_pos][0]
                bit_count = len(div_records[div_pos])
                compressed_bits = prev_compressed_bits_record[prev_div_pos]
                if len(compressed_bits) == 0 or compressed_bits[3 + bit] - compressed_bits[2 + bit] < len(div_record[div_pos]):
                    is_found = 0
                    break
                compressed_bits_record.append(compressed_bits[bit])
                cur_bit_count += len(div_record[div_pos])
                div_pos += 1
                if sum(len(div_record[i]) for i in range(div_pos)) == sum(len(prev_div_record[i]) for i in range(prev_div_pos + 1)):
                    prev_div_pos += 1
            if not is_found:
                continue
            is_sat = rec_explore_sum_3_trees(bit_len, target, target_bits, bit_num, branch_bits, branch_sum, compressed_bits_record, div_record, stat_box)
            if is_sat:
                return is_sat
    return 0

def explore_sum_3_trees(l, target):
    if target > 3 * max(l):
        return 0, [0]
    bit_len = get_bit_len(max(max(l), target)) + 1
    bit_ar2 = to_bit_ar2(l, bit_len)
    bit_ar2.sort()
    prev_compressed_bits_record = [to_compressed_bits(bit_ar2)]
    target_bits = to_rev_bits(target, bit_len)
    prev_bit_num = -1
    prev_branch_bits = [0 for i in range(bit_len)]
    prev_branch_sum = 0
    prev_div_record = ((0, 0, 0),)
    stat_box = [0]
    is_sat = rec_explore_sum_3_trees(bit_len, target, target_bits, prev_bit_num, prev_branch_bits, prev_branch_sum, prev_compressed_bits_record, prev_div_record, stat_box)
    return is_sat, stat_box

def test(bit_len, n, iter_count):
    num_limit = 2**bit_len
    max_complexity = 0
    for i in range(iter_count):
        target = rnd(3 * num_limit)
        l = [rnd(num_limit) for i in range(n)]
        is_sat, stat_box = explore_sum_3_trees(l, target)
        max_complexity = max(max_complexity, stat_box[0])
        is_sat1 = get_is_sum_3(l, target)
        if is_sat != is_sat1:
            print("EXCEPTION:")
            print("is_sat, is_sat1 =", is_sat, is_sat1)
            print("l, target =", l, target)
            return
    print("max_complexity =", max_complexity)

test(10, 10, 100)

```

Complexity in worst case is hard to compute, so I computed average complexity empirically (in stat\_box). When $n = \text{bit\_len}$ is made larger 2 times, complexity increases approx. 3.75 times (~ ${n\*\text{bit\_len}}$). Running time of standard algorithm increases 7.5 times (~ $n^2\*{\text{bit\_len}}$). Running time of my algorithm grows faster than complexity but only because I decided to not overcomplicate it (and thus hide main idea). I made comments on slow lines.


