Java solution to Codility CountDiv problem (Lesson 5 – Prefix Sums) which scored 100%. The problem is to calculate number of integers divisible by a given number form a sequential range of integers. The strategy is to find the first and last non zero divisors and perform simple subtraction and division to get total number of divisors.
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
42
public class CountDiv {
public int solution(int A, int B, int K) {
int divisors = 0;
//nothing to do when K > B
if(K > B) {
if(A == 0 || B == 0) {
return 1; //K mod 0 == 0 so count a single divisor
}
return 0; //no divisors when A, B both != 0
}
if(A == 0) {
divisors++; //K mod 0 == 0
}
int updatedA = A;
if(K > A) {
updatedA = K; //skip checking all values < K
}
int firstNonZeroDivisor = 0;
int lastNonZeroDivisor = 0;
for(int i=updatedA; i<=B; i++) { if(i % K == 0) { firstNonZeroDivisor = i; break; } } for(int i=B; i>=updatedA; i--) {
if(i % K == 0) {
lastNonZeroDivisor = i;
break;
}
}
if(firstNonZeroDivisor == 0 && lastNonZeroDivisor == 0) {
divisors = 0;
}
else {
divisors += ((lastNonZeroDivisor - firstNonZeroDivisor) / K) + 1;
}
return divisors;
}
}
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
41
42
43
44
45
46
47
48
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson05.prefixsums.CountDiv;
public class CountDivTests {
private CountDiv solution;
@BeforeTest
public void setUp() {
solution = new CountDiv();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 5, 11, 2, 3 },
new Object [] { 6, 11, 2, 3 },
new Object [] { 0, 11, 5, 3 },
new Object [] { 0, 11, 12, 1 }, //K>B, A==0
new Object [] { 1, 11, 12, 0 }, //K>B, A>0
new Object [] { 0, 0, 12, 1 }, //K>B, A==0, B==0
new Object [] { 11, 33, 3, 8 },
new Object [] { 10, 10, 5, 1 }, //A = 10, B = 10, K in {5,7,20}
new Object [] { 10, 10, 7, 0 }, //A = 10, B = 10, K in {5,7,20}
new Object [] { 10, 10, 20, 0 }, //A = 10, B = 10, K in {5,7,20}
new Object [] { 33, 33, 33, 1 }, //A == B
new Object [] { 100000, 1000000, 1000, 901 },
new Object [] { 1000, 10000, 10, 901 },
new Object [] { 100, 1000, 1, 901 },
new Object [] { 0, 2000000000, 2000000000, 2 }, //max B
new Object [] { 2000000000, 2000000000, 2000000000, 1 }, //max A, B
new Object [] { 100, 123000000, 2, 61499951 }, //A = 100, B=123M+, K=2
new Object [] { 101, 123000000, 10000, 12300 }, //A = 101, B = 123M+, K = 10K
};
}
@Test(dataProvider = "test1")
public void verifySolution(int pA, int pB, int pK, int pExpected) {
Assert.assertEquals(solution.solution(pA, pB, pK), pExpected);
}
}