Getting 'Time limit exceeded' for the problem NOTATRI. Please help. What's wrong with my code?

general
, ,
1

#include

using namespace std;

int main()
{
unsigned long int i, x, y, z, counter = 1, a, b, c, ans=0;

int n;

cin >> n;

while(n>0)
{

    unsigned long int arr[n];

    for(i=0;i<n;i++)
    {
        cin >> arr[i];
    }

    for(x=0;x<=(n-3);x++)
    {
        for(y=(x+1);y<=(n-2);y++)
        {
            for(z=(y+1);z<=(n-1);z++)
            {

            a = arr[x];
            b = arr[y];
            c = arr[z];

            while(counter <= 3)
            {
                if((a+b)<c)
                {
                    ans++;
                }

                x = a;

                a = b;

                b = c;

                c = x;

                counter++;
            }

            counter = 1;
        }
    }
}

cout << ans << endl;

ans = 0;

cin >> n;

}

return 0;

}

2

The 3 nested FOR loops are giving you complexity of n^3.You can eliminate the third loop by using the binary search to find the smallest element greater than arr[x]+arr[y].

link for binary search…its much more than searching an element in the array

http://www.quora.com/Binary-Search/What-is-binary-search

1 Like