Practers.
Get Started
Interview Questions/Coding/Prison Camera Pass Code

Prison Camera Pass Code

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Prison Camera Pass Code

Guruji needs a pass-code to disable the prison cameras. You are given an N x N matrix where each cell is either a positive distinct value or -1, meaning blocked. You may move between non-blocked cells in four directions. For every non-blocked cell with value x, its sed-value is the sum of all values y such that y is a multiple of x and y is not reachable from x. For a blocked cell, the sed-value is -1. Return the sum of all sed-values modulo 1000000007.

Examples

Example 1
Input: 
3
2 -1 6
-1 -1 -1
3 -1 12
Output: 
43

Explanation: The blocked cells contribute -5. The unreachable multiple sums of positive cells contribute 48.

Approach hint

Cells in the same connected component are reachable from each other.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp