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.
[cc lang="java" escaped="true"] package com.codility.lesson05.prefixsums; 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; } } [/cc]
TestNG test cases for this problem which all passed:
[cc lang="java" escaped="true"] package test.com.codility.lesson05.prefixsums; 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); } } [/cc]