Search code examples
scalafunctional-programmingfactors

Need help to check scala code can be made concise. Find all factors of n

Below implementation is to find all factors of given 'n' using scala. Can this scala code be concise ? Please note that the below code has O(sqrt(n)).

    @scala.annotation.tailrec
    def helper(n: Int, current: Int, acc: List[Int]): List[Int] = {
      if (current > math.sqrt(n)) acc
      else if (n % current == 0) {
        val a = n / current
        val b = n / a
        helper(n, current + 1, acc :+ a :+ b)
      } else helper(n, current + 1, acc)
    }

    helper(A, 1, List.empty[Int]).sorted.toArray

I am not looking for the below solution because this is O(n) solution.

   def factors(n: Int): List[Int] = {
     (1 to n).filter(n % _ == 0)
   }
Solution 
  •  def factors(n: Int): List[Int] = {
     (1 to n).filter(n % _ == 0)
   }

    Is indeed O(n).

    But

    def factors(n: Int) = 
  (1 to sqrt(n).toInt).filter(n % _ == 0).flatMap { k => Seq(k, n/k) }

    is O(sqrt(n)) :)