== code(c) |
def 4sum(A):

  S = {}

  sums = {}

  for a in A:
    for b in A:

      S[a + b] = (a, b)

      sums[a + b] = (a, b)

  for c in A:
    for d in A:
      if -(c + d) in sums:

        print (S[-(c + d)][0], S[-(c + d)][1], c, d)

        print (sums[-(c + d)][0], sums[-(c + d)][1], c, d)

        return
  print "No solution."

The naive solution goes through all possible values of k and takes $O(n)$ time.
The baby-step, giant-step algorithm solves the problem more efficiently using the meet in the middle trick.

Let's write k = $i([sqrt(n)] + 1) + j$

Let's write k = $i[sqrt(n)] + j$

Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.

Replacing k in the equality we get $p^(i ([sqrt(n)] + 1) + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^(i[sqrt(n)] + 1)^ = qp^-j^ (mod n)$.

Replacing k in the equality we get $p^(i[sqrt(n)] + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^i[sqrt(n)]^ = qp^-j^ (mod n)$.

At this point we can brute force through the numbers on each side of the equality and find a colision.
The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.

public

protected