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 116, 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); } }
Code language: Java (java)

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); } }
Code language: Java (java)

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; } }
Code language: Java (java)

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)); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments