count the sum of a subset of an array without bruteforcing it

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.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top