CountDiv – Codility – Solution

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]