Grid Products Without the Own Cell

Medium

You get a rectangular integer table table with n rows and m columns. Build a table of the same size where cell [i][j] holds the product of every number in table except table[i][j], taken modulo 12345. Note that 12345 is not prime, so you cannot simply divide the total product by the cell's own value under the modulus. Aim for O(n · m).

Example 1

table=[[2, 5], [3, 1]] → [[15, 6], [10, 30]]

Top left: 5 · 3 · 1 = 15, top right: 2 · 3 · 1 = 6, bottom row: 2 · 5 · 1 = 10 and 2 · 5 · 3 = 30. All are below 12345, so the remainder leaves them unchanged.

Example 2

table=[[12345, 7, 4]] → [[28, 0, 0]]

The first cell gets 7 · 4 = 28. Both other products include the factor 12345, so their remainder is 0.

Example 3

table=[[6], [9]] → [[9], [6]]

Constraints

1 ≤ n, m
2 ≤ n · m ≤ 10⁵
All rows have the same length m
1 ≤ table[i][j] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix Prefix Sum

Similar problems

Largest Light Square Medium Neighbourhood Sums in a Grid Medium K-th Largest Corner XOR Medium Three Heaviest Diamonds Medium Balanced Square in a Grid Medium

Input

table=[[2, 5], [3, 1]]

Expected

[[15, 6], [10, 30]]

Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.