Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
The Problem Statement
1.2.
Example
2.
Approach 
2.1.
Algorithm
2.2.
Program
2.3.
Input
2.4.
Output
2.5.
Time Complexity
2.6.
Space Complexity
3.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Ujjawal Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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;
}

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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Key Takeaways

In this blog, we have learned an approach to solving the problem, the maximum perimeter of the quadrilateral formed by choosing sides from the given array

Check out the following problems - 

If you want to explore more such problems then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Previous article
Check if Two Line Segments Intersect
Next article
Count Number of Intersection Points for Given Lines Between (i, 0) and (j, 1)
Live masterclass