Count divisors algorithm in immutable/pure functional Scala

Problem

\(1\) has only 1 factor - \(1\), \(6\) has 4 - \(1, 2, 3, 6\), \(36\) has 9 - \(1, 2, 3, 4, 6, 9, 12, 18, 36\). It's similar to problems on:

  • On Codility: CountFactors - Count factors of given number n.

Solution

def countDivisorsFor(n: Int): Int = {
  def nIsSquareOf(i: Int): Boolean = i * i == n
  def nHasFactor(i: Int): Boolean = n % i == 0
  (1 to Math.sqrt(n).toInt).view
    .collect({
      case i if nIsSquareOf(i) => 1
      case i if nHasFactor(i)  => 2
    })
    .sum
}

Test cases

assert(countDivisorsFor(24) == 8)
assert(countDivisorsFor(1) == 1)
assert(countDivisorsFor(2) == 2)
assert(countDivisorsFor(3) == 2)
assert(countDivisorsFor(4) == 3)
assert(countDivisorsFor(5) == 2)
assert(countDivisorsFor(6) == 4)
assert(countDivisorsFor(36) == 9)
assert(countDivisorsFor(1020) == 24)
assert(countDivisorsFor(Int.MaxValue) == 2)

Scala Concepts

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")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

assert(
  (1 to 10)
    .map { num =>
      if (num % 3 == 0) Some("Fizz")
      else if (num % 5 == 0) Some("Buzz")
      else None
    }
    .flatten
    .toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz")
)

Collect can be used on any collection, including Streaming collections like LazyList

Def Inside Def

A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.

def exampleDef(input: String): String = {
  def surroundInputWith(char: Char): String = s"$char$input$char"
  surroundInputWith('-')
}
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")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

Range

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

In Functional Programming languages, a representation often refers to the fact that evaluation of the thing is not done immediately, bringing performance benefits.

For example, `(1 to n)` is just a structure that literally says "1 to n". Only when you convert it to a list, or "force" it, does it go through the full range.

From algorithm perspective, this means that you can perform complex yet efficient computations in a fraction of code compared to other languages which all perform eager evaluation.

Also refer to: View

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))
View

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

In the example below, we can see the view in action:

var counted = 0

val resultingList = List(1, 2, 3, 4).view
  .map { num =>
    counted = counted + 1
    num + 1
  }
  .take(2)
  .toList

assert(resultingList == List(2, 3))

assert(counted == 2)

If we add a side-effect inside a map (don't do this normally!), We note that items 3 and 4 are never touched/evaluated, meaning we perform a "lazy" computation.

This is very similar to an Iterator, except views can be Indexed, and also reversed, which is a tremendously useful fact when dealing with arrays, for example when you want to zip two arrays together, such as in CheckArrayIsAPalindrome

On views, you can perform almost any typical collection operation, such as `maxBy`, `count`, `flatMap` and so forth.

And you can get views from almost any data type. Benefits other than lazy computation include potentially fusing of operations by the Java compiler, because instead of creating a new list for every stage, you evaluate new items one-by-one, meaning that if there are any optimisations to be made per one-item basis, you may get a performance boost.

Explanation

The most straightforward approach is to check from \(1\) all the way up to \(n\) and count number of times \(n\) is divisible in that range (and also check for squares). This has complexity \(O(n)\). But we can do better, because there is no larger factor than \(\sqrt{n}\), which means we can lower complexity to \(O(\sqrt{n})\).

If a number is not a square, then every divisor under a square root has a corresponding divisor above the square root - meaning we count it twice. If a number is square, this rule applies to every number except the square root - in which case, we count it only once.