baalazamon - 2 months ago 53

Scala Question

I am trying to implement LCM in one line in Scala.

This is how I've implemented it with 2 functions:

`def gcd(a: BigInt, b: BigInt):BigInt=if (b==0) a.abs else gcd(b, a%b)`

def lcm(list: Seq[BigInt]):BigInt=list.foldLeft(BigInt(1))((a, b) => (a/gcd(a,b))*b)

How would you convert gcd into a lambda inside lcm?

Answer

You need a GCD calculation that isn't recursive.

```
def lcm(list: Seq[BigInt]):BigInt=list.foldLeft(1:BigInt){(a,b) => b*a / Stream.iterate((a,b)){case (x,y) => (y, x%y)}.dropWhile(_._2 != 0).head._1.abs}
```

(Here it is in a *slightly* more readable format.)

```
def lcm(list: Seq[BigInt]):BigInt=list.foldLeft(1:BigInt){
(a, b) => b * a /
Stream.iterate((a,b)){case (x,y) => (y, x%y)}.dropWhile(_._2 != 0).head._1.abs
}
```