Count sum of a subset of an array without bruteforcing it

Question

I'll start by explaining step by step what I have to do. First I make an array containing N prime numbers that I create like this:

bool isPrime(int n) {
    if(n <= 1) return false;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}

int p[n + d], j = 0;
for(int i = 0; j < n + d; i++) {
    if(isPrime(i)) {
            p[j] = i;
            j++;
    }
}

I then create a target array Q that I'm going to be using for the calculations:

int q[n];
for(int i = 0; i < n; i++) {
    q[i] = p[i] * p[i + d];
}

Now that I have the traget array Q[N] I need to count how many times this equation is true A + B + C + D = E, where {A, B, C, D, E} are items from the array Q and A <= B <= C <= D. I tried this solution, but it's bruteforcing it and for bigger numbers it just takes minutes to calculate, which is not what I want.

int amount = 0;
for(int i = 1; i < n; i++) {
    for(int j = i - 1; j >= 0; j--) {
        for(int k = j; k >= 0; k--) {
            for(int l = k; l >= 0; l--) {
                for(int m = l; m >= 0; m--) {
                    if(q[j] + q[k] + q[l] + q[m] == q[i])
                        amount++;
                }
            }
        }
    }
}
cout << amount << endl;

For example if I input 15 for N and 1 for D the output should be 2 because:

6 + 15 + 323 + 323 = 667
6 + 143 + 221 + 1147 = 1517

But the code has to be optimized enough to calculate fast for N and D up to 2500.

I hope I explained my problem as much I could, but if you have any additional questions please ask right away. — timbo, Oct 23 '20 at 14:47
"*so it doesn't really work.*". Can you be more specific? Show an input, expected output, and the results you actually get. Also, it's nice to see a [mre]. That makes it easier for us to test the program, and help you out. — cigien, Oct 23 '20 at 14:48
For example if I input 15 for N and 1 for D the output should be 2 because: 6 + 15 + 323 + 323 = 667 6 + 143 + 221 + 1147 = 1517 But my approach returns 0, because it checks sums like these: 6 + 6 + 221 + 437 = 670 (so not 667, because it chose wrong items to sum up) 6 + 35 + 323 + 1147 = 1511 (instead of 1517 because it chose wrong items again) — timbo, Oct 23 '20 at 14:52
Thanks, but you should add that info to the question, not as a comment. — cigien, Oct 23 '20 at 14:54
And when you used your debugger to run your program, what did you see? This is precisely what a debugger is for. If you don't know how to use a debugger this is a good opportunity to learn how to use it to run your program one line at a time, monitor all variables and their values as they change, and analyse your program's logical execution flow. Knowing how to use a debugger is a required skill for every C++ developer, no exceptions. With your debugger's help you should be able to quickly find all problems in this and all future programs you write, without having to ask anyone for help. — Sam Varshavchik, Oct 23 '20 at 14:54
I'll do that right now, sorry for all those mistakes but I'm a new user. — timbo, Oct 23 '20 at 14:54
@SamVarshavchik I've updated the question, my solution doesn't consider all possible combinations of items and in return gives incorrect results. Could you suggest how I might loop through all possible combinations of 4 items lower than Q[I] to check if the sum of those items will equal to Q[I]? — timbo, Oct 23 '20 at 14:58
@SamVarshavchik I've updated the question with a working solution, but it's bruteforcing and it works incredibly slow for higher numbers. Could you help me make it more optimized? — timbo, Oct 23 '20 at 15:35
The question reads like it's from some contest/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program runs slow and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Oct 23 '20 at 15:43
@SamVarshavchik It is, I'm not trying to learn C++, my goal here is to learn the pattern to somehow optimize / solve this problem. I'm pretty sure I won't find the answer to this in a textbook, that's why I'm asking here. — timbo, Oct 23 '20 at 15:46
Oh, but you ***do*** need to learn C++ in order to do this. If the goal is to get the sum of `E`, and the 1st value in the array is `x`, then the solution includes `x` plus whatever from the rest of the array adds up to `E-x`, or `E` withour `x`. That's a recursive algorithm. This sets the upper limit of the complexity, for all of this to O^2, instead of O^5, three orders of magnitude faster than five nested for-loops. But to correctly implement it, you ***do*** need to learn C++ to 1) implement recursion correctly, 2) know how to use containers to keep track of all `x`s, on each step. — Sam Varshavchik, Oct 23 '20 at 15:57

score 3 · Accepted Answer · answered Oct 23 '20 at 15:55

To optimize this you have to invest your mathematical knowledge.

You should start from calculating prime using Sieve of Eratosthenes or some better algorithm.

Then note that all your q but first must be odd. All primes except 2 are odd and all their multiplication is odd too. As a result only first item in q is even.

Why this is important? Your sum has even number of elements, so to be able to have odd outcome which could match E in q, A must be equal to first element of q since it only even value in q.

So you have only 3 free parameters: B, C and D and E can be calculated and check if it exists.

You can iterate over B, C, D and then binary search for E in q. This will gives algorithm with complexity O(n^3 log n) which is great comparing to your O(n^5).

You can use unordered_set to match E in O(1) time instead of O(log n) time. So final algorithm easily ca be O(n^3).

I'm quite sure you can find this kind tricks more effectively. Possibly knowledge of d value could be used in some way to avoid some iterations.

Thank you so much. I'll try to implement your suggestions into my code. From what I've checked using my bruteforce solution, value of d cannot really be used in any way, except if it's 0 then there are no sums in the given range. — timbo, Oct 23 '20 at 16:06
Is using member function find() the way to check if element is in the unordered_set you mentioned? — timbo, Oct 23 '20 at 17:33
or [count](https://en.cppreference.com/w/cpp/container/unordered_set/count) which is more handy. — Marek R, Oct 23 '20 at 20:31

score 1 · Answer 2 · answered Oct 23 '20 at 16:36

I have one trick to improve @MarekR's answer from time O(n^3) to O(n^2 log(n)). (Unfortunately it also needs O(n^2) memory.)

As noted, A has to be the first element. So we just have to find the other four elements.

Now here is the trick. Generate one array of tuples (B+C, B, C) with B < C. And another array of tuples (E-D, E, D) with D < E. Sort both arrays. Now walk them in parallel, looking to match up cases where A + B+C = E-D. Filter out the cases where D <= C and voila!

Generating the arrays is O(n^2). Sorting them is O(n^2 * log(n)). Walking them in parallel and grouping by value is O(n^2). Processing a group of matches with m1 entries in the first array and m2 in the second is O(m1 * m2). You are generating extra matches per answer, but given how few answers there are, I believe that this is negligible. Which makes it O(n^2 log(n)).

chux - Reinstate Monica · Answer 3 · 2020-10-26T03:01:02.440

Code can do better than O(n^3)

Use math knowledge.

For A+B+C+D=E as prime to be true, consider the case where A+B+C+D are all odd. In that case, the sum E of 4 odd numbers is an even. Since the only even prime is 2 and sum of 4 odd primes is more than 2, A,B,C,D can not be all odds. Thus A==2.

Form an array BC containing all combinations of [0...N)[B..N) and 3 items: B, C, Sum B+C. Sort by the Sum. O(N * N * log(N)). I suspect the sorted list can be formed perhaps even closer to O(N * N), given the initial list of primes is itself ordered. Hmmm.
Form an array DE in similar fashion with the difference of E-D.
Walk array BC and then walk DE in the reverse direction looking for A+B+C+D=E.

Estimate O(N * N)* log(N)) after prime table made.

For prime, use Sieve of Eratosthenes

You have to do step 3 for `N` values of `E`. Which makes this `O(N^3)`. — btilly, Oct 23 '20 at 16:37

Count sum of a subset of an array without bruteforcing it

3 Answers3