Count factors/divisors of an integer in pure-functional immutable Scala

Algorithm goal

A number \(y\) is a factor of \(x\) if \(x\) is divisible by \(y\). Find the number of distinct factors of a number \(x\).

For example, 2 has two factors: \(1\) and \(2\). 16 has 5 factors: \(1\), \(2\), \(4\), \(8\), and \(16\).

This problem is similar to the codility problem CountFactors - Count factors of given number n.

1234567891516Total count
Divides 16?5
Factor count so far122333344445

Explanation

In a brute-force approach, for number \(n\), we can check for all numbers that are divisible, up to \(n\).

However, there is a more efficient approach, in particular if we consider that for every factor that is under \(\sqrt{n}\), there a corresponding factor to be counted that is above \(\sqrt{n}\), meaning every divisor under the square root has a corresponding divisor above it - 2 divisors. (this is © from www.scala-algorithms.com)

The rest of the Explanation is available for subscribers.

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

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

Scala Concepts & Hints

Collect

'collect' allows you to use Pattern Matching, to filter and map items.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

Read more

Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

Read more

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

View

The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

Read more

Algorithm in Scala

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

This solution is available for purchase!

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

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

Test cases in Scala

assert(countFactors(1) == 1)
assert(countFactors(2) == 2)
assert(countFactors(3) == 2)
assert(countFactors(4) == 3)
assert(countFactors(5) == 2)
assert(countFactors(6) == 4)
assert(countFactors(16) == 5)
assert(countFactors(24) == 8)
assert(countFactors(36) == 9)
assert(countFactors(Int.MaxValue) == 2)
def countFactors(n: Int): Int = ???