C++ – Count all possible scalene triangle with length of each side smaller than N

  c++, c++14

With 3 <= N <= 100000, I tried the following O(n^2) algo but I want it to be efficient, O(n)
please help with homework 😀

typedef long long ll;
int n;
int solve(int n)
{
    int ans=0;
    for(int i = n; i >= 3; i--)
    {
        int j = 1, k = i -1;
        while(j < k)
        {
            if(j + k > i)
            {
                ans += k - j;
                k--;
            }

            else
                j++;
        }
    }
    return ans;
}

Source: Windows Questions C++

LEAVE A COMMENT