3,4]], B = [[5,6],[7,8]], C = [[20,22],[43,50]] Output: False Explanation: C is not the correct product of A and B.

Solution

Method 1 – Freivald's Randomized Verification

Intuition

Instead of computing A × B directly, use a random vector to probabilistically check if C = A × B. If C ≠ A × B, the algorithm will detect the error with high probability after a few iterations.

Approach

Repeat the following steps k times (for higher confidence):
1. Generate a random vector r of size n with entries 0 or 1.
2. Compute Br = B × r.
3. Compute ABr = A × (B × r).
4. Compute Cr = C × r.
5. If ABr ≠ Cr, return False.
If all iterations pass, return True (with high probability).

Code

[{"language":"Python","code":"import random\nclass Solution:\n    def freivalds(self, A: list[list[int]], B: list[list[int]], C: list[list[int]], k: int = 10) -> bool:\n        n = len(A)\n        for _ in range(k

Related Tags