In a range of numbers, count the numbers divisible by a specific integer

Algorithm goal

In a range \(5\) to \(15\), there are \(4\) numbers divisible by \(n = 3\): \(6\), \(9\), \(12\) and \(15\). Compute this for a generic \(n\) (all non-negative numbers)

In Codility, there is a similar problem 'CountDiv'.

Explanation

A brute-force method will have a complexity that depends strictlyon the size of the input number.

Notice however that the count of numbers divisible by\(3\), up to \(15\), is \(5\) (\(3, 6, 9, 12, 15\)). If we do that with respect to a range, we need to just take the difference between counts up to the end of the range, and the counts up to the start of the range (excluding the number itself). (this is © from www.scala-algorithms.com)

Also if the number \(0\) is in range, count is increased by 1 because \(0\) is divisible by all numbers (except \(0\), of course).

The rest of the Explanation is available for subscribers.

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Scala Concepts & Hints

Range

The (1 to n) syntax produces a "Range" which is a representation of a sequence of numbers.

assert((1 to 5).toString == "Range 1 to 5")

assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")

assert((1 to 5).toList == List(1, 2, 3, 4, 5))

Read more

Algorithm in Scala

13 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for access!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Test cases in Scala

assert(countDivisibles(5 to 15, divisor = 3) == 4)
assert(countDivisibles(0 to Int.MaxValue, divisor = Int.MaxValue) == 2)
assert(countDivisibles(0 to 0, divisor = 3) == 1)
assert(countDivisibles(1 to Int.MaxValue, divisor = Int.MaxValue / 2) == 2)
def countDivisibles(range: Range, divisor: Int): Int = ???