Find Maximum Perimeter of Quadrilateral Formed by Choosing Sides from Given Array.

Introduction

Ninja has been given a problem by his school teacher in which he has to make a quadrilateral whose sides are uniquely chosen from ‘N’ given lengths. Help ninja to determine whether he can create a quadrilateral or not. If he can, then find the maximum possible perimeter of that quadrilateral.

The above problem is a common problem based on implementation. Implementation-based coding problems are widely asked in coding contests and various coding interviews.

The Problem Statement

As discussed in the introduction section, given an array ‘ARR’ of size ‘N’, where each element ‘ARR[i]’ (0 <= ‘i’ <= ’N’) represents the length of any side. Your task is to print the maximum perimeter of the quadrilateral, which can form by choosing any four distinct sides from ‘ARR’. If it is not possible to create a quadrilateral, then print -1.

Example

• Let an array ARR = {5, 1, 5, 6, 7, 2} of size N = 6. Here, the maximum possible perimeter is 23 formed by the sides {5, 5, 6, 7}. Hence, the answer is 23.
• Let’s take an another array ARR = {10, 2, 2, 1} of size N = 4. Here, a quadrilateral can’t be formed. Hence, the answer is -1.

Approach 

The above problem can be solved by checking each possible combination of 4 sides from the given array ‘ARR’. For checking, use the property of quadrilateral, i.e., twice of the maximum among all the four sides is smaller than or equals to the perimeter, i.e., A + B + C + D > 2 * max (A, B, C, D), where ‘A’, ‘B’, ‘C’ and ‘D’ are the sides of the quadrilateral.. 

Algorithm

• Create a function maximizePerimeter(N, ARR) in which :
  • Declare variable MAX_PERIMETER = -1.
  • Run four loops inside the other one to find all the possible combinations of the four sides.
    • Declare a variable CURRENT_PERIMETER = sum of the four sides.
    • If CURRENT_PERIMETER <  2 * maximum of all four sides
    • Update MAX_PERIMETER = maximum(MAX_PERIMETER, CURRENT_PERIMETER).
• Call the above function inside the main function and print the ‘MAX_PERIMETER’ value.

Program

#include <iostream>
#include <vector>
using namespace std;

int maximizePerimeter(vector<int> &arr)
{
   // Size of the array.
   int n = arr.size();

   // Declare variable 'MAX_PERIMETER' to store the answer.
   int maxPerimeter = -1;

   for (int a = 0; a < n; a++)
   {
       for (int b = a + 1; b < n; b++)
       {
           for (int c = b + 1; c < n; c++)
           {
               for (int d = c + 1; d < n; d++)
               {
                   // Find the perimeter of the quadrilateral formed by these 4 points.
                   int currentPerimeter = arr[a] + arr[b] + arr[c] + arr[d];

                   // Check whether quadrilateral exist or not.
                   if (currentPerimeter > 2 * max(max(arr[a], arr[b]), max(arr[c], arr[d])))
                   {
                       if (maxPerimeter < currentPerimeter)
                           maxPerimeter = currentPerimeter;
                   }
               }
           }
       }
   }
   return maxPerimeter;
}

int main()
{

   // Taking the number of elements in the array as an input.
   int n;
   cin >> n;

   // Taking the vector 'ARR' as an input.
   vector<int> arr(n);
   for (int i = 0; i < n; i++)
   {
       cin >> arr[i];
   }

   // Call function 'maximizePerimeter()'.
   int maxPerimeter = maximizePerimeter(arr);

   // Print answer.
   cout << maxPerimeter;

   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

10
4 3 4 45 22 11 33 43 23 12

Output

144

Time Complexity

O(N ^ 4), where ‘N’ is the number of elements in the array.

Four loop runs inside each other, and each runs up to ‘N’ iteration. Hence, its time complexity is O(N^4).

Space Complexity

O(1).

The above algorithm doesn’t use any extra space except a few variables. Hence, its space complexity is O(1).