LeetCode #3725 — HARD

Count Ways to Choose Coprime Integers from Rows

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

You are given a m x n matrix mat of positive integers.

Return an integer denoting the number of ways to choose exactly one integer from each row of mat such that the greatest common divisor of all chosen integers is 1.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: mat = [[1,2],[3,4]]

Output: 3

Explanation:

Chosen integer in the first row	Chosen integer in the second row	Greatest common divisor of chosen integers
1	3	1
1	4	1
2	3	1
2	4	2

3 of these combinations have a greatest common divisor of 1. Therefore, the answer is 3.

Example 2:

Input: mat = [[2,2],[2,2]]

Output: 0

Explanation:

Every combination has a greatest common divisor of 2. Therefore, the answer is 0.

Constraints:

1 <= m == mat.length <= 150
1 <= n == mat[i].length <= 150
1 <= mat[i][j] <= 150

Step 01

Brute Force Baseline

Problem summary: You are given a m x n matrix mat of positive integers. Return an integer denoting the number of ways to choose exactly one integer from each row of mat such that the greatest common divisor of all chosen integers is 1. Since the answer may be very large, return it modulo 109 + 7.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Math · Dynamic Programming

Example 1

[[1,2],[3,4]]

Example 2

[[2,2],[2,2]]

Step 02

Core Insight

What unlocks the optimal approach

Use dynamic programming.
Use <code>dp[row][g]</code>, where <code>row</code> is the current row and <code>g</code> is the current gcd value.
Initialize the first row: for each value <code>v</code> in row 0 do <code>dp[0][v] += 1</code>.
For a row <code>i</code>, use the values from the previous row <code>i - 1</code> to build the values: for each previous gcd <code>g</code> and each value <code>v</code> in row <code>i</code>.
The final answer is <code>dp[n-1][1]</code> (number of ways with gcd 1).

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
// package main
// 
// import "slices"
// 
// // https://space.bilibili.com/206214
// func countCoprime1(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	mx := 0
// 	for _, row := range mat {
// 		mx = max(mx, slices.Max(row))
// 	}
// 
// 	m := len(mat)
// 	memo := make([][]int, m)
// 	for i := range memo {
// 		memo[i] = make([]int, mx+1)
// 		for j := range memo[i] {
// 			memo[i][j] = -1 // -1 表示没有计算过
// 		}
// 	}
// 	var dfs func(int, int) int
// 	dfs = func(i, g int) (res int) {
// 		if i < 0 {
// 			if g == 1 {
// 				return 1
// 			}
// 			return
// 		}
// 		p := &memo[i][g]
// 		if *p != -1 { // 之前计算过
// 			return *p
// 		}
// 		for _, x := range mat[i] {
// 			res += dfs(i-1, gcd(g, x))
// 		}
// 		res %= mod
// 		*p = res // 记忆化
// 		return
// 	}
// 	return dfs(m-1, 0)
// }
// 
// func countCoprime2(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	mx := 0
// 	for _, row := range mat {
// 		mx = max(mx, slices.Max(row))
// 	}
// 
// 	m := len(mat)
// 	f := make([][]int, m+1)
// 	for i := range f {
// 		f[i] = make([]int, mx+1)
// 	}
// 	f[0][1] = 1
// 	for i, row := range mat {
// 		for g := 0; g <= mx; g++ {
// 			res := 0
// 			for _, x := range row {
// 				res += f[i][gcd(g, x)]
// 			}
// 			f[i+1][g] = res % mod
// 		}
// 	}
// 	return f[m][0]
// }
// 
// func gcd(a, b int) int {
// 	for a != 0 {
// 		a, b = b%a, a
// 	}
// 	return b
// }
// 
// const maxVal = 151
// 
// var divisors [maxVal][]int
// 
// func init() {
// 	for i := 1; i < maxVal; i++ {
// 		for j := i; j < maxVal; j += i {
// 			divisors[j] = append(divisors[j], i)
// 		}
// 	}
// }
// 
// func countCoprime(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	// 预处理每行的因子个数
// 	divisorCnt := make([][]int, len(mat))
// 	mx := 0
// 	for i, row := range mat {
// 		rowMax := slices.Max(row)
// 		mx = max(mx, rowMax)
// 		divisorCnt[i] = make([]int, rowMax+1)
// 		for _, x := range row {
// 			for _, d := range divisors[x] {
// 				divisorCnt[i][d]++
// 			}
// 		}
// 	}
// 
// 	cntGcd := make([]int, mx+1)
// 	for i := mx; i > 0; i-- {
// 		// 每行选一个 i 的倍数的方案数
// 		res := 1
// 		for _, cnt := range divisorCnt {
// 			if i >= len(cnt) || cnt[i] == 0 {
// 				res = 0
// 				break
// 			}
// 			res = res * cnt[i] % mod // 乘法原理
// 		}
// 
// 		for j := i; j <= mx; j += i {
// 			res -= cntGcd[j] // 注意这里有减法，可能导致 res 是负数
// 		}
// 
// 		cntGcd[i] = res % mod
// 	}
// 	return (cntGcd[1] + mod) % mod // 保证结果非负
// }

// Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
package main

import "slices"

// https://space.bilibili.com/206214
func countCoprime1(mat [][]int) int {
	const mod = 1_000_000_007
	mx := 0
	for _, row := range mat {
		mx = max(mx, slices.Max(row))
	}

	m := len(mat)
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, mx+1)
		for j := range memo[i] {
			memo[i][j] = -1 // -1 表示没有计算过
		}
	}
	var dfs func(int, int) int
	dfs = func(i, g int) (res int) {
		if i < 0 {
			if g == 1 {
				return 1
			}
			return
		}
		p := &memo[i][g]
		if *p != -1 { // 之前计算过
			return *p
		}
		for _, x := range mat[i] {
			res += dfs(i-1, gcd(g, x))
		}
		res %= mod
		*p = res // 记忆化
		return
	}
	return dfs(m-1, 0)
}

func countCoprime2(mat [][]int) int {
	const mod = 1_000_000_007
	mx := 0
	for _, row := range mat {
		mx = max(mx, slices.Max(row))
	}

	m := len(mat)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, mx+1)
	}
	f[0][1] = 1
	for i, row := range mat {
		for g := 0; g <= mx; g++ {
			res := 0
			for _, x := range row {
				res += f[i][gcd(g, x)]
			}
			f[i+1][g] = res % mod
		}
	}
	return f[m][0]
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

const maxVal = 151

var divisors [maxVal][]int

func init() {
	for i := 1; i < maxVal; i++ {
		for j := i; j < maxVal; j += i {
			divisors[j] = append(divisors[j], i)
		}
	}
}

func countCoprime(mat [][]int) int {
	const mod = 1_000_000_007
	// 预处理每行的因子个数
	divisorCnt := make([][]int, len(mat))
	mx := 0
	for i, row := range mat {
		rowMax := slices.Max(row)
		mx = max(mx, rowMax)
		divisorCnt[i] = make([]int, rowMax+1)
		for _, x := range row {
			for _, d := range divisors[x] {
				divisorCnt[i][d]++
			}
		}
	}

	cntGcd := make([]int, mx+1)
	for i := mx; i > 0; i-- {
		// 每行选一个 i 的倍数的方案数
		res := 1
		for _, cnt := range divisorCnt {
			if i >= len(cnt) || cnt[i] == 0 {
				res = 0
				break
			}
			res = res * cnt[i] % mod // 乘法原理
		}

		for j := i; j <= mx; j += i {
			res -= cntGcd[j] // 注意这里有减法，可能导致 res 是负数
		}

		cntGcd[i] = res % mod
	}
	return (cntGcd[1] + mod) % mod // 保证结果非负
}

# Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
#
# @lc app=leetcode id=3725 lang=python3
#
# [3725] Count Ways to Choose Coprime Integers from Rows
#

# @lc code=start
from math import gcd
from collections import Counter
from typing import List

class Solution:
    def countCoprime(self, mat: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # Initialize dp with the first row
        # dp[g] stores the number of ways to have a running GCD of g
        dp = [0] * 151
        
        row_counts = Counter(mat[0])
        for val, count in row_counts.items():
            dp[val] = (dp[val] + count) % MOD
            
        # Process subsequent rows
        for i in range(1, len(mat)):
            new_dp = [0] * 151
            row_counts = Counter(mat[i])
            
            # We only need to iterate through existing GCDs in dp
            # Since values are small (<=150), we can just iterate 1..150
            # Optimization: collect current valid gcds to avoid iterating 150 times if sparse
            current_gcds = [g for g in range(1, 151) if dp[g] > 0]
            
            if not current_gcds:
                return 0
                
            for g in current_gcds:
                ways = dp[g]
                for val, count in row_counts.items():
                    new_g = gcd(g, val)
                    new_dp[new_g] = (new_dp[new_g] + ways * count) % MOD
            
            dp = new_dp
            
        return dp[1]

# @lc code=end

// Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
// package main
// 
// import "slices"
// 
// // https://space.bilibili.com/206214
// func countCoprime1(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	mx := 0
// 	for _, row := range mat {
// 		mx = max(mx, slices.Max(row))
// 	}
// 
// 	m := len(mat)
// 	memo := make([][]int, m)
// 	for i := range memo {
// 		memo[i] = make([]int, mx+1)
// 		for j := range memo[i] {
// 			memo[i][j] = -1 // -1 表示没有计算过
// 		}
// 	}
// 	var dfs func(int, int) int
// 	dfs = func(i, g int) (res int) {
// 		if i < 0 {
// 			if g == 1 {
// 				return 1
// 			}
// 			return
// 		}
// 		p := &memo[i][g]
// 		if *p != -1 { // 之前计算过
// 			return *p
// 		}
// 		for _, x := range mat[i] {
// 			res += dfs(i-1, gcd(g, x))
// 		}
// 		res %= mod
// 		*p = res // 记忆化
// 		return
// 	}
// 	return dfs(m-1, 0)
// }
// 
// func countCoprime2(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	mx := 0
// 	for _, row := range mat {
// 		mx = max(mx, slices.Max(row))
// 	}
// 
// 	m := len(mat)
// 	f := make([][]int, m+1)
// 	for i := range f {
// 		f[i] = make([]int, mx+1)
// 	}
// 	f[0][1] = 1
// 	for i, row := range mat {
// 		for g := 0; g <= mx; g++ {
// 			res := 0
// 			for _, x := range row {
// 				res += f[i][gcd(g, x)]
// 			}
// 			f[i+1][g] = res % mod
// 		}
// 	}
// 	return f[m][0]
// }
// 
// func gcd(a, b int) int {
// 	for a != 0 {
// 		a, b = b%a, a
// 	}
// 	return b
// }
// 
// const maxVal = 151
// 
// var divisors [maxVal][]int
// 
// func init() {
// 	for i := 1; i < maxVal; i++ {
// 		for j := i; j < maxVal; j += i {
// 			divisors[j] = append(divisors[j], i)
// 		}
// 	}
// }
// 
// func countCoprime(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	// 预处理每行的因子个数
// 	divisorCnt := make([][]int, len(mat))
// 	mx := 0
// 	for i, row := range mat {
// 		rowMax := slices.Max(row)
// 		mx = max(mx, rowMax)
// 		divisorCnt[i] = make([]int, rowMax+1)
// 		for _, x := range row {
// 			for _, d := range divisors[x] {
// 				divisorCnt[i][d]++
// 			}
// 		}
// 	}
// 
// 	cntGcd := make([]int, mx+1)
// 	for i := mx; i > 0; i-- {
// 		// 每行选一个 i 的倍数的方案数
// 		res := 1
// 		for _, cnt := range divisorCnt {
// 			if i >= len(cnt) || cnt[i] == 0 {
// 				res = 0
// 				break
// 			}
// 			res = res * cnt[i] % mod // 乘法原理
// 		}
// 
// 		for j := i; j <= mx; j += i {
// 			res -= cntGcd[j] // 注意这里有减法，可能导致 res 是负数
// 		}
// 
// 		cntGcd[i] = res % mod
// 	}
// 	return (cntGcd[1] + mod) % mod // 保证结果非负
// }

// Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3725: Count Ways to Choose Coprime Integers from Rows
// package main
// 
// import "slices"
// 
// // https://space.bilibili.com/206214
// func countCoprime1(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	mx := 0
// 	for _, row := range mat {
// 		mx = max(mx, slices.Max(row))
// 	}
// 
// 	m := len(mat)
// 	memo := make([][]int, m)
// 	for i := range memo {
// 		memo[i] = make([]int, mx+1)
// 		for j := range memo[i] {
// 			memo[i][j] = -1 // -1 表示没有计算过
// 		}
// 	}
// 	var dfs func(int, int) int
// 	dfs = func(i, g int) (res int) {
// 		if i < 0 {
// 			if g == 1 {
// 				return 1
// 			}
// 			return
// 		}
// 		p := &memo[i][g]
// 		if *p != -1 { // 之前计算过
// 			return *p
// 		}
// 		for _, x := range mat[i] {
// 			res += dfs(i-1, gcd(g, x))
// 		}
// 		res %= mod
// 		*p = res // 记忆化
// 		return
// 	}
// 	return dfs(m-1, 0)
// }
// 
// func countCoprime2(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	mx := 0
// 	for _, row := range mat {
// 		mx = max(mx, slices.Max(row))
// 	}
// 
// 	m := len(mat)
// 	f := make([][]int, m+1)
// 	for i := range f {
// 		f[i] = make([]int, mx+1)
// 	}
// 	f[0][1] = 1
// 	for i, row := range mat {
// 		for g := 0; g <= mx; g++ {
// 			res := 0
// 			for _, x := range row {
// 				res += f[i][gcd(g, x)]
// 			}
// 			f[i+1][g] = res % mod
// 		}
// 	}
// 	return f[m][0]
// }
// 
// func gcd(a, b int) int {
// 	for a != 0 {
// 		a, b = b%a, a
// 	}
// 	return b
// }
// 
// const maxVal = 151
// 
// var divisors [maxVal][]int
// 
// func init() {
// 	for i := 1; i < maxVal; i++ {
// 		for j := i; j < maxVal; j += i {
// 			divisors[j] = append(divisors[j], i)
// 		}
// 	}
// }
// 
// func countCoprime(mat [][]int) int {
// 	const mod = 1_000_000_007
// 	// 预处理每行的因子个数
// 	divisorCnt := make([][]int, len(mat))
// 	mx := 0
// 	for i, row := range mat {
// 		rowMax := slices.Max(row)
// 		mx = max(mx, rowMax)
// 		divisorCnt[i] = make([]int, rowMax+1)
// 		for _, x := range row {
// 			for _, d := range divisors[x] {
// 				divisorCnt[i][d]++
// 			}
// 		}
// 	}
// 
// 	cntGcd := make([]int, mx+1)
// 	for i := mx; i > 0; i-- {
// 		// 每行选一个 i 的倍数的方案数
// 		res := 1
// 		for _, cnt := range divisorCnt {
// 			if i >= len(cnt) || cnt[i] == 0 {
// 				res = 0
// 				break
// 			}
// 			res = res * cnt[i] % mod // 乘法原理
// 		}
// 
// 		for j := i; j <= mx; j += i {
// 			res -= cntGcd[j] // 注意这里有减法，可能导致 res 是负数
// 		}
// 
// 		cntGcd[i] = res % mod
// 	}
// 	return (cntGcd[1] + mod) % mod // 保证结果非负
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n × m)

Space

O(n × m)

Approach Breakdown

RECURSIVE

O(2ⁿ) time

O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING

O(n × m) time

O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.