7
\$\begingroup\$

Problem Statement:

Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as lengths of three sides of triangles.

Input: The first line of the input contains T denoting the number of testcases. First line of test case is the length of array N and second line of test case are its elements.

Output: Number of possible triangles are displayed to the user.

Constraints:

\$1 \le T \le 200\$
\$3 \le N \le 10^7\$
\$1 \le \mathrm{arr}[i] \le 10^3\$

Example:

Input:

2
3
3 5 4
5
6 4 9 7 8

Output:

1
10

Algorithm:

The efficient \$O(n^2)\$ algorithm for solving this problem has been explained here.

Let \$a\$, \$b\$ and \$c\$ be three sides. The below condition must hold for a triangle (Sum of two sides is greater than the third side) i) \$a + b > c\$ ii) \$b + c > a\$ iii) \$a + c > b\$

Following are steps to count triangle.

  1. Sort the array in non-decreasing order.

  2. Initialize two pointers i and j to first and second elements respectively, and initialize count of triangles as 0.

  3. Fix i and j and find the rightmost index k (or largest arr[k]) such that arr[i] + arr[j] > arr[k]. The number of triangles that can be formed with arr[i] and arr[j] as two sides is k – j. Add k – j to count of triangles.

    Let us consider arr[i] as \$a\$, arr[j] as \$b\$ and all elements between arr[j+1] and arr[k] as \$c\$. The above mentioned conditions (ii) and (iii) are satisfied because arr[i] < arr[j] < arr[k]. And we check for condition (i) when we pick k.

  4. Increment j to fix the second element again.

    Note that in step 3, we can use the previous value of k. The reason is simple, if we know that the value of arr[i] + arr[j-1] is greater than arr[k], then we can say arr[i] + arr[j] will also be greater than arr[k], because the array is sorted in increasing order.

  5. If j has reached end, then increment i. Initialize j as i + 1, k as i+2 and repeat the steps 3 and 4.

Code Implementation (in C++):

This is my implementation of the algorithm in C++ (using vectors instead of raw arrays):

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;
int triangles (vector<int> &V, int N);

int main () {
    int T;
    cin >> T;
    vector<int> V;
    for (int i = 0; i < T; i++)
    {
        int N;
        cin >> N;
        for (int j = 0; j < N; j++)
        {
           int temp;
           cin >> temp;
           V.push_back(temp);
        }
        cout << triangles (V, N) << endl;
        V.clear();
    }
    return 0;
}

int triangles (vector<int> &V, int N)
{
    int sum = 0;
    sort(V.begin(), V.end());
    for (int i = 0; i <= N-3; i++)
    {   
        int k = i + 2;
        for (int j = i + 1; j <= N-2; j++)
        {
            while (k < N && V[k] < V[i] + V[j])
                k++;
            sum += k-j-1;
        }
    }
    return sum;
}

Problem:

The code gives the perfectly correct output for any input, however, when I submit the code on GeekForGeeks Practice, it says

Your program took more time than expected (Time Limit Exceeded). Expected Time Limit < 2.656sec. Hint: Please optimize your code and submit again.

At this point, I'm not sure how to optimize my code. Any ideas? Do I necessarily need to use an array instead of a vector in order to speed up the program?

\$\endgroup\$
  • 1
    \$\begingroup\$ Choose telling names for your variables. From a 9 second glance at the source code, I could not recognise the algorithm described following The efficient O(n²) … explained here.: document what problem is solved with what algorithm in your program source. \$\endgroup\$ – greybeard Aug 27 at 4:02
  • 1
    \$\begingroup\$ There's a comment on the linked page that says: "I am very surprised that qsort() is not giving a TLE, whereas std::sort() does." Perhaps that's one place to start looking for an answer? \$\endgroup\$ – user1118321 Aug 27 at 4:13
  • 1
    \$\begingroup\$ @user1118321 That almost guarantees that the commentator is misusing std::sort. \$\endgroup\$ – L. F. Aug 27 at 4:16
  • 1
    \$\begingroup\$ If \$N\$ might be \$10^7\$ then you don't want to use a \$\Theta(N^2)\$ algorithm. \$\endgroup\$ – Peter Taylor Aug 27 at 13:42
  • 1
    \$\begingroup\$ See AJNeufeld's answer. \$\endgroup\$ – Peter Taylor Aug 27 at 19:09
7
\$\begingroup\$

Don't use using namespace std;. It is extremely bad practice and will ruin your life. You will have trouble on common identifiers like count, size, etc. See Why is “using namespace std;” considered bad practice? for more information.

The input format is extremely awkward, but this seems to be beyond your control, so I'll leave it alone.

Instead of using a linear search as you are doing in your loop, it might be beneficial to do a binary search if the amount of data is large. (This needs some testing.) Also, use standard algorithms to make your code more readable.

Also, in this very case, a dynamic vector may not be the best way to appeal to the timer. (I'm not sure how I would phrase that.) reserve may help. You can try using a static vector like this one because you know that the size is below a limit.

\$\endgroup\$
7
\$\begingroup\$

The statement V.push_back(temp); can be inefficient, as the vector V may need to be reallocated multiple times.

Use std::vector::reserve(N) to ensure sufficient space exists in the vector before reading in the data to avoid multiple reallocations.


\$3 \le N \le 10^7\$
\$1 \le \mathrm{arr}[i] \le 10^3\$

With \$10^7\$ pigeons and \$10^3\$ holes, many holes can have over 10,000 pigeons! You might want to consider an array of counts indexed by side length. No sort required; it is automatically sorted. But your algorithm will need considerable reworking.

\$\endgroup\$
3
\$\begingroup\$

Even after using reserve, as suggested by @L.F. and @AJNeufeld, there was no considerable speedup and it was still timing out. So I decided to use dynamically allocated arrays instead. I also removed using namespace std, and instead only imported those std functions which are required in the program.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using std::cout;
using std::cin;
using std::endl;
using std::sort;

long long int triangles (int arr[], int N);

int main () {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int N;
        cin >> N;
        int *arr = new int[N];
        for (int j = 0; j < N; j++)
        {
        cin >> arr[j];
        }
        cout << triangles (arr, N) << endl;
        delete arr;
    }
    return 0;
}

long long int triangles (int arr[], int N)
{
    long long int sum = 0;
    sort(arr, arr+N);
    for (int i = 0; i <= N-3; i++)
    {   
        int k = i + 2;
        for (int j = i + 1; j <= N-2; j++)
        {
            while (k < N && arr[k] < (arr[i] + arr[j]))
                k++;
            sum += k-j-1;
        }
    }
    return sum;
}

Note that the data type of the sum which is returned by the triangles() function must be at least long long int, as it otherwise exceeds the range of regular int.

\$\endgroup\$
  • 2
    \$\begingroup\$ That geeksforgeeks page is very wrong. Prior to C++20, the range of int is an implementation-defined superset of integers in [-32767, 32767], and the range of long int is an implementation-defined superset of integers in [-2,147,483,647, 2,147,483,647]. You should use long long int. I recommended that you use a more accurate C++ reference like en.cppreference.com. \$\endgroup\$ – L. F. Aug 27 at 11:45
  • \$\begingroup\$ @L.F. Thanks, I will check that reference. By the way, do you happen to have any idea about why dynamically allocated arrays outperform vectors in this context? According to the discussion here, they should approximately have the same speed/performance. \$\endgroup\$ – S.D. Aug 27 at 11:51
  • 1
    \$\begingroup\$ Vectors are more flexible and do a lot of bookkeeping for you. It is much more than just a dynamically allocated array. So with extremist timing, it can be "observably" slower than arrays. In practice, this small difference probably doesn't matter at all. \$\endgroup\$ – L. F. Aug 27 at 11:54
  • 1
    \$\begingroup\$ Note that std:;cin, std::cout and std::endl are used only inside main(), so the scope of those using statements can be reduced. Similarly, std::sort is used only in triangles() - and there, only once, so is the using really necessary? \$\endgroup\$ – Toby Speight Aug 27 at 12:20
  • \$\begingroup\$ @L.F., surely the type to use (ever since C++11 came out) is one of the types defined in cstdint? (Well, or it would be if any of them were wide enough. The output requires 117 bits in the worst case, and 128-bit integer types are non-standard extensions). \$\endgroup\$ – Peter Taylor Aug 27 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.