Java solution to Codility CountFactors problem (Lesson 10 – Prime and composite numbers) which scored 100%. The problem is to count all the factors of a given integer N.
Note: using a brute force approach (checking every number below N) wouldn’t pass this problem because it would take too long.
The strategy is to find all factors by only checking up to square root of N and incrementing by 2 each time N % i == 0.
Reference
Prime and composite numbers tutorial (PDF – Codility)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class CountFactors {
public int solution(int N) {
int factors = 0;
int squareRootN = (int) Math.sqrt(N);
if(Math.pow(squareRootN, 2) != N) {
squareRootN++; //round up for any non-perfect squares
}
else { //perfect squares have an additional factor
factors++;
}
for(int i=1; i<squareRootN; i++) {
if(N % i == 0) {
factors += 2;
}
}
return factors;
}
}
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
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson10.primecomposite.CountFactors;
public class CountFactorsTests {
private CountFactors solution;
@BeforeTest
public void setUp() {
solution = new CountFactors();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 1, 1 },
new Object [] { 2, 2 }, //1, 2
new Object [] { 3, 2 }, //1, 3
new Object [] { 4, 3 }, //1, 2, 4
new Object [] { 10, 4 }, //1, 2, 5, 10
new Object [] { 24, 8 }, //1, 2, 3, 4, 6, 8, 12, 24
new Object [] { 25, 3 }, //1, 5, 25
new Object [] { 36, 9 }, //1, 2, 3, 4, 6, 9, 12, 18, 36
new Object [] { 56, 8 }, //1, 2, 4, 7, 8, 14, 28, 56
new Object [] { 100, 9 }, //1, 2, 4, 5, 10, 20, 25, 50, 100
};
}
@Test(dataProvider = "test1")
public void verifySolution(int pA, int pExpected) {
Assert.assertEquals(solution.solution(pA), pExpected);
}
}