Two equivalent codes giving different run time on GeeksforGeeks platform?

Question

I was solving a question on GeeksforGeeks regarding finding the total number of triangles possible using the three different array elements as sides of the triangle from an unsorted array arr[] of size n. This is the first implementation for the above question. ...

int findNumberOfTriangles(int arr[], int n)
    {
        // code here
        sort(arr,arr+n);
        
        int i,j,k,count=0;
        
        for(i=0;i<n-2;i++)//first side of triangle
        {
            k=i+2; // third side of triangle , ie. rightmost element initialized
            for(j=i+1;j<n;j++)    //second side of triangle
            {    
                // search for all elements less than sum of the 
                // first and second side of the triangle
                while(k<n)
                {
                    if(arr[i]+arr[j]>arr[k]) 
                        k++;                
                }
                
                count=count+ k-j-1; //adds no of triangle possible for each pair of sides
            }
        }
        
        return count;
    }

... The above implementation is correct and should have O(N^2) time complexity. For the above code, I am getiing a TLE(Time Limit exceeded) from GeeksforGeeks platform with expected time limit=1.02 sec.

Now compare the following implementation to the above implementation.

int findNumberOfTriangles(int arr[], int n)
        {
            // code here
            sort(arr,arr+n);
            
            int i,j,k,count=0;
            
            for(i=0;i<n-2;i++)//first side of triangle
            {
                k=i+2; // third side of triangle , ie. rightmost element initialized
                for(j=i+1;j<n;j++)    //second side of triangle
                {    
                    // search for all elements less than sum of the 
                    // first and second side of the triangle
                    while(k<n && arr[i]+arr[j]>arr[k])
                         k++; 
                    
                    count=count+ k-j-1; //adds no of triangle possible for each pair of sides
                }
            }
            
            return count;
        }

The implementation differs only in the while loop inside second for loop.I moved the if condition from inside of the while body to the condition declaration part by using the Logical AND operation. The time complexity for this is same as the first implementation :O(N^2).

But , this implementation was accepted by GeeksforGeeks with time taken = (0/1.0).

Can someone tell me why is there so much performance difference between two equivalent pieces of code. Is this due to GeeksforGeeks platform or due to the features of the C++ language. GeeksforGeeks uses g++5.4 compiler

Link : https://practice.geeksforgeeks.org/problems/count-possible-triangles-1587115620/1

Answer 1

They are not equivalent.

            while(k<n)
            {
                if(arr[i]+arr[j]>arr[k]) 
                    k++;                
            }

On the first element that is encountered for which the if condition is false, this loop will continue to loop forever, because k won't be incremented.

This one:

      while(k<n && arr[i]+arr[j]>arr[k])
                     k++; 

Stops the loop when either k<n or on the first element for which arr[i]+arr[j]>arr[k] is false.

Consider this example

          k            arr[i]+arr[j]>arr[k]
          1            true
          2            true 
          3            false 
         ...           false
          n

This first counts till k = 2 and then never stops, because k is not incremented anymore. The second loops till k = 2 and stops when k = 3.

PS: (Disclaimer_ I'll tell you my personal view, though it is was it is) Geeksforgeeks is a good place to find poor tutorials, questionable code that often is non-standard but claims to be good for beginners (it isn't) and misleading and often wrong explanations. Mistakes can happen here as well, but then usually someone comments and answers can be fixed (or downvoted when they are too wrong). If you want to learn C++ I suggest you this instead: The Definitive C++ Book Guide and List