Four Elements from GeeksForGeeks

Question

This is a question from GeeksForGeeks

Given an array of integers, find a combination of four elements in the array whose sum is equal to a given value X.

Input: First line consists of T test cases. First line of every test case consists of an integer N, denoting the number of elements in an array. Second line consists of N spaced array elements. Third line of every test case X.

Output: Single line output, print 1 if combination is found else 0.

Constraints: 1<=T<=100

1<=N<=100

Example: Input: 1 6 1 5 1 0 6 0 7

Output: 1

Here is the code

#include <iostream>
#include <cassert>
#include <vector>

int main() {
    int t, n, val, x, sum = 0;
    bool found = false;
    std::cin >> t;
    assert(t >= 1 && t <= 100);

    while (t--)
    {
        std::cin >> n;
        assert(n >=1 && n <= 100);
        std::vector<int> vec(n);
        for (int i = 0; i < n; i++)
        {
            std::cin >> val;
            vec[i] = val;
        }

        std::cin >> x;

        for (int i = 0; i < n - 3; i++)
        {
            for (int j = i + 1; j < n - 2; j++)
            {
                for (int k = j + 1; k < n - 1; k++)
                {
                    for (int l = k + 1; l < n; l++)
                    {
                        sum = vec[i] + vec[j] + vec[k] + vec[l];
                        if (sum == x)
                        {
                            found = true;
                            break;
                        }
                    }
                }
            }
        }

        if (found == true)
        {
            std::cout << 1 << std::endl;
        }
        else
        {
            std::cout << 0 << std::endl;
        }
    }
    return 0;
}

How to optimise this code?

Answer 1

It's good that you've already found the optimisation of starting j at i and k at j and l at k. There are other potential optimisations of a similar nature, such as keeping track of the maximum and minimum entries in the array and breaking out of loops when it becomes clear that you cannot reach or will overshoot x.

From a microoptimisation perspective, using std::array is often preferable to std::vector. You can't use std::array without knowing ahead of time what size to make it, and n could change run by run. All is not lost: n is always guaranteed to be no more than 100 and you can probably afford a hundred element array.

However, your algorithm is still \$ O(n^4) \$, (as intuitively shown by the four nested loops) which means it will rapidly slow down as n increases.

Once you get to the innermost loop, you no longer need to check all possible values of l. You just need to check whether x - (i + j + k) is present in the remainder of the list. There are many algorithms that allow for checking whether something is present given a bit of foresight in choosing a data structure: for example sorting the list would allow you to use binary search in log time, or populating a hash map would typically get you constant time. However, that would still be an \$ O(n^3) \$ algorithm.

There is an option available for getting down to an \$ O(n^2) \$ algorithm by using the principles of dynamic programming: solve a smaller problem, and store the result. Specifically, it's easy to do an \$ O(n^2) \$ algorithm for finding sums of two elements. What you can do, then, is create a list of all the possible sums of pairs of elements, and if two sums of two disjoint pairs (p=i+j and q=k+l) sum to x then those four elements sum to x. As explained above, it is possible to short circuit out of the innermost loop, so rather than checking each value of q you can just check whether x-p is in the set (I recommend using unordered_set from the standard library) of sums of pairs. You can also arbitrarily require an order on p and q, such as requiring that p<q. That means that you only have to check values of p up to a total of x/2, and if you go past that then you can immediately conclude that the required sum is not available.

There is an important caveat here: you would need to ensure that there is no overlap between the numbers used in the partial results p and q. That's a bit of a fiddly implementation, but essentially you'd want a struct to store the totals along with which individual elements went into it.

I do not believe better than \$ O(n^2)\$ is achievable.

Answer 2

When to use Assert
Generally assert() is a debugging tool. The GeekforGeeks website itself warns against using it in certain cases.

If the NODEBUG compilation flag is used in the file the assertion is removed.

It might be better to use if statements and write the output to std::cerr. That would provide a much more meaningful error message.

Reduce Complexity, Follow SRP
The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows: A class should have only one reason to change.

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

The more separate functions there are the easier it is to understand or read the code. This also makes it easier for any programmer to maintain or debug the code.

The main() function could be broken up into at multiple functions. The main() function should generally just control the program and handle any exceptions that get to that point.

An example of a decent main() function for this program might be:

int main() {
    int t;
    std::cin >> t;
    assert(t >= 1 && t <= 100);
    int x;

    while (t--)
    {
        std::vector<int> vec = getTestCase(x);

        std::cout << ((executeTestCase(vec, x)) ? 1 : 0) << std::endl;
    }

    return 0;
}

The first function that might be of use is an test case input function.

std::vector<int> getTestCase(int &x)
{
    int n;
    std::cin >> n;
    assert(n >= 1 && n <= 100);
    std::vector<int> vec(n);
    for (int i = 0; i < n; i++)
    {
        int val;
        std::cin >> val;
        vec.push_back(val);
    }    

    std::cin >> x;

    return vec;
}

The second function that might be of use would be a that finds if there are values that meet the proper conditions.

bool executeTestCase(std::vector<int> vec, int x)
{
    bool found = false;
    int sum = 0;
    int n = vec.size();

    for (int i = 0; i < n - 3; i++)
    {
        for (int j = i + 1; j < n - 2; j++)
        {
            for (int k = j + 1; k < n - 1; k++)
            {
                for (int l = k + 1; l < n; l++)
                {
                    sum = vec[i] + vec[j] + vec[k] + vec[l];
                    if (sum == x)
                    {
                        found = true;
                        break;
                    }
                }
            }
        }
    }    

    return found;
}

Improve Performance
Since the code is using a C++ container class, it might be possible to use iterators to improve performance. Once the code is broken up into functions and compiled -O3 it can be profiled to find where any bottlenecks exist.

Answer 3

int t, n, val, x, sum = 0;
bool found = false;
std::cin >> t;

Don’t declare all the variables up at the top — put them where first used for real.

---

Prefer prefix over postfix — it doesn’t matter for int when you don’t use the value of the expression, but more generally you will do this with iterators and “smart” objects of some kind, so don’t do things differently with int just because it doesn’t matter for this one.

---

    if (found == true)
    {
        std::cout << 1 << std::endl;
    }
    else
    {
        std::cout << 0 << std::endl;
    }

Do you understand that found is already of type bool? It is pointless and strange to compare against true or false.

Converting a bool value to an integer produces 0 or 1. So you don’t even need that test in the first place!

std::cout << found << '\n';

(that is the default for output streams, but you can also make it print “true”/“false” if you set that formatting option)

Prefer using \n over std::endl

---

You really should break up your main into separate input gathering, looping, and main algorithm functions. That will tame a lot of the local variables all by itself. So you get something like:

int main()
{
int case_count = get_case_count();
while (case_count--) {
    auto terms = get_terms();
    int x = get_x();
    auto result= solve (x, terms);
    show_results (result);
}
}

---

    std::vector<int> vec(n);
         ⋮
    vec[i] = val;

That might be how you are used to doing things in other languages, and it works as you expect for int values. But that’s not the normal way to use the container.

On the other hand, pre-allocating it like that makes it simpler to do without the hand-written loop:

std::copy_n (istream_iterator{cin}, n, vec.begin());

---

The four nested loops seem awkward and a lot of text for what it does. But, hiding that would not be easy without sacrificing precious speed.

To make it faster:

First, sort the vector of available terms.

This way, once your sum exceeds n you can quit and not try the rest of the terms at that level of the loop!

Instead of looking up all four terms and summing them in the very center of the inner loop, keep track of partial progress.

 for (int i ⋯
     int s1 = vec[i];
     if (s1+3 > x)  break;
     for (int j ⋯
         int s2 = s1 + vec[j];
         if (s2+2 > x)  break;
         for (int k ⋯
             int s3 = s2 + vec[k];
             if (s3+1 > x)  break;
             for (int m ⋯
                 int sum = s3 + vec[m];
                 if (sum == x)  return { vec[i],vec[j],vec[k],vec[m] };
                 if (sum > x)  break;
}}}}
return {0,0,0,0};

Shorting out in an outer loop saves you all the successive inner loops’ iterations for that term.