Software Engineering

# Count the divisible numbers in Java

## The challenge#

Complete the function that takes 3 numbers `x, y and k` (where `x ≤ y`), and returns the number of integers within the range `[x..y]` (both ends included) that are divisible by `k`.

More scientifically: `{ i : x ≤ i ≤ y, i mod k = 0 }`

### Example#

Given `x = 6, y = 11, k = 2` the function should return `3`, because there are three numbers divisible by `2` between `6` and `11``6, 8, 10`

• Note: The test cases are very large. You will need a O(log n) solution or better to pass. (A constant time solution is possible.)

## The solution in Java code#

Option 1:

``````class Solution {
static long divisibleCount(long x, long y, long k) {
return y / k - x / k + (x % k > 0 ? 0 : 1);
}
}
``````

Option 2:

``````public class Solution {

public static long divisibleCount(long x, long y, long k) {
return Math.floorDiv(y, k) - Math.floorDiv(x - 1, k);
}

}
``````

Option 3:

``````import java.util.stream.LongStream;
public class Solution {

public static long divisibleCount(long x, long y, long k) {
while (x % k != 0)
x++;
while (y % k != 0)
y--;
return (y - x) / k + 1;  }

}
``````

## Test cases to validate our solution#

``````import java.util.Random;
import java.util.function.LongBinaryOperator;
import org.junit.Test;
import static org.junit.Assert.assertEquals;

public class SolutionTest {
@Test
public void fixedTests() {
assertEquals( 3, Solution.divisibleCount( 6,  11,  2));
assertEquals(20, Solution.divisibleCount(11, 345, 17));
assertEquals( 1, Solution.divisibleCount( 0,   1,  7));
assertEquals( 1, Solution.divisibleCount(20,  20,  2));
assertEquals( 0, Solution.divisibleCount(20,  20,  8));
assertEquals( 1, Solution.divisibleCount(19,  20,  2));
assertEquals(11, Solution.divisibleCount( 0,  10,  1));
assertEquals( 2, Solution.divisibleCount(11,  14,  2));
assertEquals(838488366986797791L, Solution.divisibleCount(101, Long.MAX_VALUE, 11));
assertEquals(84618092081236466L, Solution.divisibleCount(1005, Long.MAX_VALUE, 109));
}

@Test
public void randomTests() {
Random rnd = new Random();
LongBinaryOperator nextLong = (a,b)->a+(long)(rnd.nextDouble()*(b-a));
for(int i=0; i<100; ++i) {
long a = nextLong.applyAsLong(10000L, Long.MAX_VALUE - nextLong.applyAsLong(45000L, 150000L));
long b = nextLong.applyAsLong(a + 1, Long.MAX_VALUE);
long k = nextLong.applyAsLong(2L, 5000L);
assertEquals(Math.floorDiv(b,k)-Math.floorDiv(a-1,k), Solution.divisibleCount(a, b, k));
}
}
}
``````