Scala algorithm: Count factors/divisors of an integer

Published , last updated

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.

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

  1. 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")
    
  2. 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")
    
  3. 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))
    
  4. View

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

Algorithm in Scala

8 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(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)

View the rest of Scala algorithms