0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ what is the question? (since it seems you have answered the question in the title yourself...) $\endgroup$ Mar 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 Gu
    Mar 17 '18 at 22:06
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.