Product of other cells in a matrix #medium #prefix
Intuition
// p = a*b*c*d
// a' = (p/a)%m
// are we allowed to do 1/a with modulo?
//
// corner case: zero if we do %M locally
//
// this is some math theory
//
// 12345 is not a prime
// if there is a group of numbers that are multiplies of 12345
// then all elements are zero except this group (if no duplicates)
//
// 12 minute hint: solve without '/', hint2: suffix-prefix
//
Division is not allowed: total product can be 0, and modulo division should be mod inverse, not allowed for 12345
Approach
flatten the matrix to make code shorter
Complexity
Time complexity: $$O(nm)$$
Space complexity: $$O(nm)$$
Code
// 90ms
fun constructProductMatrix(g: Array<IntArray>) = g.flatMap{it.toList()}.run {
val p = scan(1L) { r, t -> r * t % 12345 }
val s = reversed().scan(1L) { r, t -> r * t % 12345 }.reversed()
indices.map { p[it] * s[it+1] % 12345 }.chunked(g[0].size)
}
// 20ms
let f = g.concat();
let o = |a: &mut i64, &x: &i32| { let r = *a; *a = *a * x as i64% 12345; Some(r) };
f.iter().scan(1, o).zip(f.iter().rev().scan(1, o).collect_vec().into_iter().rev())
.map(|(p,s)| (p * s % 12345) as i32).chunks(g[0].len())
.into_iter().map(Iterator::collect).collect()
}
