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:

1
2
3
4
5

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

Option 2:

1
2
3
4
5
6
7

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 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

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));
        }
    }
}