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?

$\begingroup$ what is the question? (since it seems you have answered the question in the title yourself...) $\endgroup$– Carlo BeenakkerMar 17 '18 at 15:28

1$\begingroup$ For randomly chosen inputs, we can run the naive algorithm on the first $\Theta(\log n)$ bits to identify $O(1)$ (in expectation) possible candidates, then naively check these candidates. $\endgroup$– Yuzhou GuMar 17 '18 at 22:06
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.