5
$\begingroup$

The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there are are three arrays $X,Y,Z$, and we have to find a number per array $a\in X, b\in Y, c\in Z$ such that $a+b+c=0$. Call the first variant 3SUMx1 and the second one 3SUMx3.

Given an oracle for 3SUMx3, can we solve 3SUMx1 in linear time?

One option that comes to mind is just to create 3 replicates of the input array $S$ and run: 3SUMx3($S,S,S$). However, this may return two copies of the same item. E.g. if $S$ has only two elements, 1 and -2, then the 3SUMx1 problem has no solution, but 3SUMx3($S,S,S$) will return the fake solution $(1,1,-2)$.

I currently have a solution but it is not linear. To explain the solution, consider first the simpler problems 2SUMx1 and 2SUMx2, in which we only look for two numbers $a+b=0$ in either one array or two different arrays. Given an oracle for 2SUMx2, the problem 2SUMx1 can be solved in the following way.

Let $n$ be the number of elements in the input array $S$.

For i = 1 to log(n):
  Partition the array S to two arrays, X and Y, based on bit i of the index. I.e.:
    X contains all elements S[k] where bit i of k is 0;
    Y contains all elements S[k] where bit i of k is 1.
  Run 2SUMx2(X,Y)
  If there is a solution, return it and exit.
If no solution were found for any i, return "no solution".

This algorithm works because, if there are two different items, $a,b\in S$, whose sum is 0, then their index must have at least one bit different, say bit $i$. So, in iteration $i$ they will be in different parts and will be found by 2SUMx2($X$,$Y$). The time complexity is $O(n \log n)$.

This algorithm can be generalized to 3SUM by using trits instead of bits, and checking all possible pairs of them. The time complexity is therefore $O(n \log^2 n)$.

Is there a linear-time algorithm?

$\endgroup$
  • 1
    $\begingroup$ In 3SUMx1 there is no constraint that all elements be different, though it is meaningful to define a constrained version of 3SUMx1 along the lines you describe. $\endgroup$ – Yuval Filmus Feb 2 '15 at 14:34
  • $\begingroup$ Do you count the running time to invoke the oracle as $O(1)$ or as $O(n)$ (where $n$ is the length of the arrays passed to the oracle)? $\endgroup$ – D.W. Feb 2 '15 at 18:51
  • $\begingroup$ I think $O(n)$ makes more sense. Since the ultimate goal is to prove that these two variants have the same complexity. $\endgroup$ – Erel Segal-Halevi Feb 2 '15 at 18:57
  • $\begingroup$ @ErelSegalHalevi, that seems reasonable -- I suggest editing the question to add this detail. $\endgroup$ – D.W. Feb 2 '15 at 23:05
  • $\begingroup$ One more thought. Are you OK with giving us an oracle the following variant/generalization of 3SUMx3: given arrays $X,Y,Z$ and a target $t$, we have to find $a \in X$, $b \in Y$, and $c \in Z$ such that $a+b+c=t$. (The generalization is the target $t$; now the target can be arbitrary, instead of just zero.) If you can give me an oracle for that, plus an oracle for 2SUMx2, I think I can give you a deterministic linear-time algorithm for 3SUMx1. Is that of interest? [Note that it's clear to me whether it's even possible to solve 2SUMx2 in deterministic linear time.] $\endgroup$ – D.W. Feb 4 '15 at 22:21
6
$\begingroup$

Randomized algorithms

If you'll accept a randomized algorithm, yes, it can be done in linear time. There's a randomized algorithm whose expected running time is $O(n)$, and where the probability that it takes longer than $c \cdot n$ time is exponentially small in $c$.

Here's the idea. Randomly permute the entries of $S$, then split it into three equal-sized pieces, each of length $n/3$: let $X$ be the first one-third, $Y$ the second one-third, and $Z$ the third one-third. Now call 3SUMx1(X, Y, Z). If this finds a solution, you have a solution to the 3SUMx3 problem. Moreover, I claim that if there is a solution to the 3SUMx3 problem, then with probability at least $6/27$, this procedure finds a solution. Therefore, the expected number of times you have to repeat it (before finding the first solution) is constant.

The running time of each iteration is $O(n)$, and you do a constant number of iterations (on average), so the total expected running time is $O(n)$. The probability that you fail to find a solution after $k$ iterations is $(21/27)^k$, which is exponentially small in $k$.

Where does $6/27$ come from? Suppose there's a solution to the 3SUMx3 problem, say, $S[i]+S[j]+S[k]=0$. What is the probability that $i,j,k$ all come from different thirds of the array? This probability is $3!/3^3 = 6/27$. So, if a solution to the 3SUMx3 problem exists, then each iteration of the above procedure has at least a probability $6/27$ of finding it.

Deterministic algorithms

What about a deterministic algorithm? I don't have a specific proposal in mind, but I feel like it's plausible that this construction could be derandomized.

For instance, to give you an idea of the sort of thing I'm talking about, suppose we split the array into thirds once (deterministically). Suppose there exists a solution $S[i]+S[j]+S[k]=0$. Then there are $3^3=27$ cases for which third each $i,j,k$ falls into. After you remove symmetries, there are only $1+6+3$ cases:

  • Type A (1 case): All three indices fall in different thirds.

  • Type B (6 cases): Two of the indices fall into the same third, and the other index falls a different third.

  • Type C (3 cases): All three indices fall into the same third.

You can test for a type-A solution in $O(n)$ time, with a single invocation of the oracle: 3SUMx1(X, Y, Z). Also, you can test for a type-C solution by making three recursive calls to the same solution (one on X, one on Y, one on Z). This leaves only the question of how to test for a type-B solution. It seems like you might also be able to test for a type-B solution using a similar recursive algorithm, though I haven't tried to work out the detailed case analysis. It seems not impossible that perhaps some ideas along these lines could lead to a deterministic algorithm -- though I haven't worked out the details and I'm just speculating at this point.

$\endgroup$
  • $\begingroup$ Thanks. I also thought about the deterministic algorithm but got stuck at type B. $\endgroup$ – Erel Segal-Halevi Feb 4 '15 at 19:35
0
$\begingroup$

My original post regarding a variant of the 3SUMx3 problem was in error. However, I believe I was in the right path and have edited the post with a new algorithm.

Let's say we have a set S which needs to be split into 3 sets such that we can then run the 3SUMx3 algorithm on it. Also let's assume that the entries in S form an alphabet of range (0, M] such that for some a, b, c in alphabet M, a + b + c = M, aka 0 (and M % M = 0).

So for numbers from 0 - 256, we would have 64 + 64 + 128 = 256 = 0.

I propose we sort the entries in set S and put them into three buckets with the following ranges. X = (0, M/3] Y = (M/3, M/6] Z = (2M/3, M].

The property of the sets is such that, sum of any three elements within set X would not equal to M since they are all less than a third of M.

Any element in set Y can be expressed as M/3 + an equivalent element from set X. Consequently sum of any three elements from set Y would also never equal M (aka 0). For some a1, b1, and c1 from set Y, a1 + b1 + c1 = 3* M/3 + (a + b + c) where a, b, and c would be some elements from set X. Since (a + b + c) cannot equal M (aka 0), a1 + b1 + c1 cannot equal 0.

The same can also be said about elements from set Z. Elements a2, b2, c2 being from set Z, it can be said that a2 + b2 + c2 equals 3 * 2M/3 + (a + b + c) where a, b, and c are elements from set X and thus a2 + b2 + c2 cannot equal M (aka 0).

So with these three sets as defined, if we were to run the 3SUMx3 algorithm on sets X, Y, and Z, I theorize that we would be able to definitively know if we have a solution.

Does that sound correct ? comments ?

$\endgroup$
  • 1
    $\begingroup$ “Examining elements from set X, they either end in 00 or 11 and the sum of any odd number of the elements would never result in a zero.” Why? $\endgroup$ – xskxzr Aug 9 at 2:54
  • $\begingroup$ Thank you xskxzr. I edited my post to correct the algorithm. $\endgroup$ – Kedar Aug 9 at 23:01

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.