Java solution to Codility MinPerimeterRectangle problem (Lesson 10 – Prime and composite numbers) which scored 100%. The problem is to find the minimal perimeter of a rectangle whose area equals N.
The strategy is to:
- compute each factor using same technique as CountFactors problem (using square root method)
- calculate second factor by simple division since know first factor and N
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
public class MinPerimeterRectangle {
public int solution(int N) {
int squareRootN = (int) Math.sqrt(N);
int factor2 = 0;
int perimeter = 0;
int minPerimeter = Integer.MAX_VALUE;
if(Math.pow(squareRootN, 2) != N) {
squareRootN++; //round up for any non-perfect squares
}
else { //perfect square root won't be reached inside loop so calculate and set min perimeter
minPerimeter = 2 * (squareRootN + squareRootN);
}
for(int i=1; i<squareRootN; i++) {
if(N % i == 0) {
//calculate 2nd factor by simple division since know 1st factor and N
factor2 = N / i;
perimeter = 2 * (factor2 + i);
minPerimeter = Math.min(perimeter, minPerimeter);
}
}
return minPerimeter;
}
}
TestNG test cases for this problem which all passed:
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
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson10.primecomposite.MinPerimeterRectangle;
public class MinPerimeterRectangleTests {
private MinPerimeterRectangle solution;
@BeforeTest
public void setUp() {
solution = new MinPerimeterRectangle();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 1, 4 }, //2x(1+1)=4
new Object [] { 2, 6 }, //2x(1+2)=6
new Object [] { 3, 8 }, //2x(1+3)=8
new Object [] { 4, 8 }, //2x(1+4)=10, 2x(2+2)=8
new Object [] { 10, 14 }, //2x(1+10)=22, 2x(2+5)=14
new Object [] { 24, 20 }, //2x(1+24)=50, 2x(2+12)=48, 2x(3+8)=22, 2x(4+6)=20
new Object [] { 25, 20 }, //2x(1+25)=52, 2x(5+5)=20,
new Object [] { 30, 22 }, //2x(1+30)=62, 2x(2+15)=34, 2x(3+10)=26, 2x(5+6)=22
new Object [] { 36, 24 }, //2x(1+36)=72, 2x(2+18)=40, 2x(3+12)=30, 2x(4+9)=26, 2x(6+6)=24,
new Object [] { 56, 30 }, //2x(7+8)=30
new Object [] { 100, 40 }, //2x(10+10)=40
};
}
@Test(dataProvider = "test1")
public void verifySolution(int pA, int pExpected) {
Assert.assertEquals(solution.solution(pA), pExpected);
}
}