Hi5 Interview Question
Software Engineer / Developers/* Created by Gaurav Kumar on 24th March
* The following conditions have been taken cared of
* 1. If for some perimeter we can find two edges that are both prime then there are two case:
* Case 1:the minimum length edge is 1. For e.g. we have (2,3), then we have to see if (1, 2*3)
* which will have the same area as (2,3), has the perimeter less than the maximum perimeter entered.
* If it does not have then it should not be included in the list to be printed.
* Case 2: Minimum edge length is not 1. In this case there is no other set of pairs that can produce
* the same area and hence that perimeter can not be in the list to be printed.
* 2. In order to determine if exists another pair with the same area within the constraints of maximum
* perimeter and minimum length, we have to find the smallest number that divides the length completely and then
* compute the new perimeter and see if it is in range. E.g. perimeter 46 with one of the dimensions as (4,19) smallest
* length lets say is 1 and maximum parameter 64. 2 is the smallest no. that divides 4 completly so, we can build a
* rectangle with l = 4/2 = 2 and b = 19*2 = 38. The perimeter in this case will 2*40 = 80 > 64. So this doesnot work.
* Let's try the same thing with taking breadth now. The smallest no. that divides 19 is 19 itself as it is prime and so
* the new dimensions of the rectangle will be 76, 1. In this case too, perimeter exceeds 64 and hence we can conclude that
* this perimeter 46 won't be on the list.
*/
public class YourClass
{
//Return true if the no. passes is a Prime number
public static boolean isPrime(int num)
{
boolean flag = true;
for(int i=2; i<=num/2;i++)
if(num % i == 0)
{
flag = false;
break;
}
return flag;
}
public static void main(String[] args)
{
int i,j,min_length = 0,l,b,max_perimeter, min_perimeter, count = 0;
boolean flag=true, flag1=true,flag2 = true;
//minimum length of the rectangle
min_length = Integer.parseInt(args[0]);
//Maximum perimeter of the rectangle
max_perimeter = Integer.parseInt(args[1]);
min_perimeter = 4 * min_length;
//Checking for the wrong inputs
if(min_length < 1 || max_perimeter < min_perimeter || max_perimeter%2 !=0)
{
System.out.println("Incorrect Input");
return;
}
for(i = min_perimeter+2; i<= max_perimeter ; i= i+2)
{
// for every parameter in the set U we will pick up each one
// one by one and check for all the possible dimensions if
// it satisfies all the constraints.
j = 0;
l = j+min_length; //Length of the rectangle
b = i/2 - l; //Width of the rectangle
while(l<=b)
{
flag = flag1 = flag2 = true;
//Checking if one of l and b is prime and the other is equal to the minimum length, then the perimeter can't be included
if((l == min_length && isPrime(b)) || (b==min_length && isPrime(l)))
{
flag = false;
break;
}
//find out the lowest no that divides the length and breadth
for(int k=2;k<=l;k++)
if(l%k == 0)
{
//Checking if all the constraints of min length and max parameter is satisfied
if(l/k < min_length || 2*(l/k + b*k) > max_perimeter)
flag1 = false;
break;
}
for(int k=2;k<=b;k++)
if(b%k == 0)
{
//Checking if all the constraints of min length and max parameter is satisfied
if(2*(b/k + l*k) > max_perimeter || b/k < min_length)
flag2 = false;
break;
}
//End of IF
//If both flag1 and flag2 are false it means this perimeter should not be included, hence break.
if(!flag1 && !flag2)
break;
j++;
l = j+min_length;
b = i/2 - l;
}//End of WHILE Loop
if(flag && (flag1 || flag2))
{
count++;
if(count == 1)
System.out.print(i);
else
System.out.print("," + i);
}
}//End of OUTER For Loop
}//End of Main
} //End of Class
Read the Question carefully. It says "Find the subset of perimeters in set U where all of the possible dimensions for a perimeter in the subset have areas common with the areas of one or more other perimeters in set U". Read last line AREA COMMON WITH ONE OR MORE OTHER PERIMETER IN SET U. So, if you chose 18 as one of the perimeter you can't chose 12.
/* Created by Gaurav Kumar on 24th March
- Gaurav May 04, 2008* The following conditions have been taken cared of
* 1. If for some perimeter we can find two edges that are both prime then there are two case:
* Case 1:the minimum length edge is 1. For e.g. we have (2,3), then we have to see if (1, 2*3)
* which will have the same area as (2,3), has the perimeter less than the maximum perimeter entered.
* If it does not have then it should not be included in the list to be printed.
* Case 2: Minimum edge length is not 1. In this case there is no other set of pairs that can produce
* the same area and hence that perimeter can not be in the list to be printed.
* 2. In order to determine if exists another pair with the same area within the constraints of maximum
* perimeter and minimum length, we have to find the smallest number that divides the length completely and then
* compute the new perimeter and see if it is in range. E.g. perimeter 46 with one of the dimensions as (4,19) smallest
* length lets say is 1 and maximum parameter 64. 2 is the smallest no. that divides 4 completly so, we can build a
* rectangle with l = 4/2 = 2 and b = 19*2 = 38. The perimeter in this case will 2*40 = 80 > 64. So this doesnot work.
* Let's try the same thing with taking breadth now. The smallest no. that divides 19 is 19 itself as it is prime and so
* the new dimensions of the rectangle will be 76, 1. In this case too, perimeter exceeds 64 and hence we can conclude that
* this perimeter 46 won't be on the list.
*/
public class YourClass
{
//Return true if the no. passes is a Prime number
public static boolean isPrime(int num)
{
boolean flag = true;
for(int i=2; i<=num/2;i++)
if(num % i == 0)
{
flag = false;
break;
}
return flag;
}
public static void main(String[] args)
{
int i,j,min_length = 0,l,b,max_perimeter, min_perimeter, count = 0;
boolean flag=true, flag1=true,flag2 = true;
//minimum length of the rectangle
min_length = Integer.parseInt(args[0]);
//Maximum perimeter of the rectangle
max_perimeter = Integer.parseInt(args[1]);
min_perimeter = 4 * min_length;
//Checking for the wrong inputs
if(min_length < 1 || max_perimeter < min_perimeter || max_perimeter%2 !=0)
{
System.out.println("Incorrect Input");
return;
}
for(i = min_perimeter+2; i<= max_perimeter ; i= i+2)
{
// for every parameter in the set U we will pick up each one
// one by one and check for all the possible dimensions if
// it satisfies all the constraints.
j = 0;
l = j+min_length; //Length of the rectangle
b = i/2 - l; //Width of the rectangle
while(l<=b)
{
flag = flag1 = flag2 = true;
//Checking if one of l and b is prime and the other is equal to the minimum length, then the perimeter can't be included
if((l == min_length && isPrime(b)) || (b==min_length && isPrime(l)))
{
flag = false;
break;
}
//find out the lowest no that divides the length and breadth
for(int k=2;k<=l;k++)
if(l%k == 0)
{
//Checking if all the constraints of min length and max parameter is satisfied
if(l/k < min_length || 2*(l/k + b*k) > max_perimeter)
flag1 = false;
break;
}
for(int k=2;k<=b;k++)
if(b%k == 0)
{
//Checking if all the constraints of min length and max parameter is satisfied
if(2*(b/k + l*k) > max_perimeter || b/k < min_length)
flag2 = false;
break;
}
//End of IF
//If both flag1 and flag2 are false it means this perimeter should not be included, hence break.
if(!flag1 && !flag2)
break;
j++;
l = j+min_length;
b = i/2 - l;
}//End of WHILE Loop
if(flag && (flag1 || flag2))
{
count++;
if(count == 1)
System.out.print(i);
else
System.out.print("," + i);
}
}//End of OUTER For Loop
}//End of Main
} //End of Class