# A New Algorithm for Solving the rSUM Problem

### EasyChair Preprint 8271

6 pages•Date: June 13, 2022### Abstract

A determined algorithm is presented for solving the rSUM problem for any natural r with a sub-quadratic assessment of time complexity in some cases. In terms of an amount of memory used the obtained algorithm is the nlog^3(n) order.

The idea of the obtained algorithm is based not considering integer numbers, but rather k (is a natural) successive bits of these numbers in the binary numeration system. It is shown that if a sum of integer numbers is equal to zero, then the sum of numbers presented by any k successive bits of these numbers must be sufficiently "close" to zero. This makes it possible to discard the numbers, which a fortiori, do not establish the solution.

**Keyphrases**: 3SUM (kSUM) problem, Structure of sumsets, computational complexity, computational geometry, knapsack problem, number theory