# A common 3SUM-hard reduction

I'm writing this to address a problem I often hear from friends. They usually get it from some technical interview.

Problem1

Let $$A$$ be an array of $$n$$ numbers, decide if there exist index $$i,j,k$$, such that $$A[i]+A[j]=A[k]$$.

The problem is 3SUM-hard. We reduce the problem 3SUM to the above problem in linear time.

Problem23SUM

Does there exist $$a,b,c\in S$$, such that $$a+b+c=0$$?

Consider a instance of 3SUM. Let $$m=3 \max(S \cup -S)+1$$. Store $$\{m\}+S$$ and $$\{2m\}-S$$ as elements in the array $$A$$.

Claim: There exist i,j,k such that $$A[i]+A[j]=A[k]$$ iff there exist $$a,b,c\in S$$ such that $$a+b+c=0$$.

If there exist $$i,j,k$$ such that $$A[i]+A[j]=A[k]$$, this implies $$A[i]=a+m,A[j]=b+m,A[k]=2m+(-c)$$ for some $$a,b,c\in S$$. The other direction is similar.

Posted by Chao Xu on 2014-04-05.
Tags: .