There is an "obvious" brute force solution, which would be to implement the algorithm exactly as the problem is stated. This is an O(N^2) solution, not so good. You can do better by simply taking a product of all of the elements of the original list, and then replacing each member of the list with the product divided by the element. So for the example above, the product = 2*4*6*8 = 384, and thus the output should be (384/2, 384/4 , 384/6, 384/8). This is O(N) solution, and that is much better. This is the best you can do in terms of speed and space, as you only keep around one extra integer in memory (the product.) However, it doesn't always work.

The problem is when there is a zero in the list. Then the above algorithm will lead to division by zero errors. Dick pointed this out, and pointed out that there are really three casses. If there is exactly one zero, then every element in the return list will be zero, except for the one at the same index as the lone zero from the input list. If there are two or more zeroes, then every element in the return list will be zero. With that in mind, here was my solution:

def wallify(list:List[Int]):List[BigInt] ={

val one = BigInt.int2bigInt(1)

val noZeroes = list.filter(_ != 0)

if (noZeroes.length == list.length){

val prod = list.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)}

list.map(prod/_)

} else if (list.length - noZeroes.length == 1){

list.map((el) =>

if (el == 0)

noZeroes.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)}

else

0

)

} else {

list.map((el) => 0)

}

}

I had to leave early, and didn't finish my code until today. Here is the code that the group, led by Bill Venners:

def wallify(input: List[Int]): List[Long] = {

def boringCalcProduct(longInput: List[Long]): Long = {

var product = 1L

for (ele <- longInput) {

product *= ele

}

product

}

def calcProduct(input: List[Long]): Long =

// input.foldLeft(1L)(_ * _)

(1L /: input)(_ * _)

val zeroCount = input.filter(_ == 0).size

val longInput: List[Long] = input.map(ele => ele.toLong)

zeroCount match {

case 0 =>

val product = calcProduct(longInput)

longInput.map(product / _)

case 1 =>

val noZero = longInput.filter(_ != 0)

val product = calcProduct(noZero)

longInput.map(ele => if (ele == 0) product else 0)

case _ =>

input.map(ele => 0L)

}

}

## 1 comment:

Haskell:wallify ls = zipWith (*) (tail (scanr (*) 1 ls)) (scanl (*) 1 ls)

Scala:def wallify(xs: Seq[Int]) = (xs.scanRight(1)(_*_).tail, xs.scanLeft(1)(_*_)).zipped.map(_*_)

This solution does not require commutativity or invertability of your binary operation, only

associativity.

Post a Comment