The algorithm counts the number of zeros in the list.
If there are no zeros, it finds the product of the entire list and
divides it by each element in the list.
If there is one zero, it finds the product of all the numbers except
zero. It returns a list of all zeros, except for the position that
originally had a zero, where it puts the calculated product.
If there are two or more zeros, it returns a list of all zeros.
The functions: multiply, lst.count, lst.map and lst.filter are all
O(N) time-complexity where N is the length of the list. The functions
lst.map and lst.filter are also O(N) space-complexity where N is the
size of the resulting list. Therefore wallify is O(N) time and O(N)
space.
(An optimal solution would be O(N) time and O(1) space if the input
was an Array[Long] and we could destructively modify the input. If the
input was an Array[Int], or we couldn't destructively modify the
input, then the optimal solution is also O(N) space, since we'd need
to copy over the input to a new Array[Long].)
--j
def multiply(lst: List[Long]): Long =
(1L /: lst)(_ * _)
def wallifyLong(lst: List[Long]): List[Long] = {
val numZeros = lst.count(_ == 0)
numZeros match {
case 0 =>
val product = multiply(lst)
lst.map(product / _)
case 1 =>
val withoutZeros = lst.filter(_ != 0)
val product = multiply(withoutZeros)
lst.map(x => if (x == 0) product else 0)
case _ =>
// numZeros >= 2
lst.map(x => 0)
}
}
def wallify(lst: List[Int]): List[Long] =
wallifyLong(lst.map(_.toLong))