Least Perimeter Problem

by

Here is a slightly edited version of the problem I got:
Given an array of integers, considering the integers as the lengths of sides of a triangle, write a function that returns the minimum perimeter of any triangle possible with these set of integers by using any three of them as the lengths of sides of the triangle. If there are no possible triangles, the function should return -1.
A note from me: Remember the rule that three given lengths will be those of the sides of a triangle if the sum of any two is greater than the third.

For example, if given integers are: 10,2,5,1,8,20
The triangle with sides 10,5,8 will be the triangle with least perimeter i.e 23
Note that the lengths 1,2,5 are not those of the sides of a triangle.

Another example: If the given integers are:5,10,18,7,8,3
Then the triangle with sides 5,7,3  will be the triangle with least perimeter i.e 15

Here take a look at the method that will do the job:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 public static int lessPer(int[] a)
 {
     int len=a.length;
     boolean done=false;
     int per=Integer.MAX_VALUE;
     for (int i=0;i<len;i++)
     {
         for (int j=i+1;j<len;j++)
         {
             for (int k=j+1;k<len;k++)
             {
                 if (a[i]+a[j]>a[k] && a[j]+a[k]>a[i] && a[i]+a[k]>a[j])
                 {
                     done|=true;
                     if (a[i]+a[j]+a[k]<per)
                         per=a[i]+a[j]+a[k];
                 }
             }
         }
     }
     return (done)? per : -1;
 }

Here is the full code to test it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
 import java.util.Scanner;
 /**
  * @author Hafiz Muhammad Umer
  */
 public class LessPerimeter {
     public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         System.out.print("How much numbers do you want to enter? ");
         int n=in.nextInt();
         int[] a=new int[n];
         for (int i=0;i<n;i++)
         {
             a[i]=in.nextInt();
         }
         int result=lessPer(a);
         System.out.println(result);
     }
     public static int lessPer(int[] a)
     {
         int len=a.length;
         boolean done=false;
         int per=Integer.MAX_VALUE;
         for (int i=0;i<len;i++)
         {
             for (int j=i+1;j<len;j++)
             {
                 for (int k=j+1;k<len;k++)
                 {
                     if (a[i]+a[j]>a[k] && a[j]+a[k]>a[i] && a[i]+a[k]>a[j])
                     {
                         done|=true;
                         if (a[i]+a[j]+a[k]<per)
                             per=a[i]+a[j]+a[k];
                     }
                 }
             }
         }
         return (done)? per : -1;
     }
     
 }

And here is the output:

How much numbers do you want to enter? 6
10
2
5
1
8
20
23

Explanation:
I am going to explain that how that method works.

  • The array we got is represented by a. The length of the array is stored in an integer at line 3.
  • We will store our result in the variable “per” defined at line 5. It is given the maximum possible value for an integer. The boolean variable at line 4 is false and it will turn true only if a possible triangle is found. It will be used at the end to decide that if we got one or more possible triangles, then we will return the perimeter (stored in variable per) and if no possible triangle is found, the boolean variable will remain false and we will return -1.
  • Now comes the loop. Here we have a triple nested loop which will test every possible group of three integers from the array. The testing is performed from lines 12 to 14. At line 12, the if statement checks whether the three lengths corresponding to the indices in the array form a triangle or not. Remember the rule that the sum of lengths of any two sides of a triangle is always greater than the length of the third side. It means that if a,b and c will be the sides of a triangle only if a+b>c and b+c>a and a+c>b. These three conditions are tested in the if statement at line 12.
  • If the “if” statement at line 12 evaluates true, the control comes to line 13 to 16. First thing it does is to make the boolean variable “done” true which we defined at the line 4. This will help us decide in the end that whether we found a triangle or not. If no triangle is found, the control will never reach the line 14 and the “done” variable will remain false.
  • Now we have found a possible triangle. At lines 15 and 16, the program checks that whether the perimeter of this triangle is less than that already stored in the variable “per”. If it is less, the value in the variable “per” is replaced by the perimeter of this triangle.
  • Now the control comes out of the loops and reaches the line 21 on which return statement is located. If no triangle was found above, the “done” variable will be false and we will have to return -1. And if one or more triangles were found, the “done” will be true and the variable “per” will contain the least perimeter and we will have to return it. So the ternary operator checks if the “done” is true, it returns “per” otherwise it returns -1. 

Extra things:

  • Check the line number 14. done|=true; will do the same thing as done=true;  Because in boolean algebra, if we apply the operator OR on true and any other variable, the answer will be always true.
  • At line number 5, Integer.MAX_VALUE gives the maximum possible value for an int variable. Also remember that Integer.MIN_VALUE gives the minimum possible value for an int.

Practice Corner:
Write code for a method that would take an array as in the above problem but it will return the maximum possible perimeter. Keep practicing. You can inbox me the code at m.me/JavaWithUmer

Do not forget to like my facebook page fb.com/JavaWithUmer and fb.com/UmerSoftwaresBlogger

Post Views: 915

Leave a Comment