LeetCode 3725 - Count Ways to Choose Coprime Integers from Rows

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Matrix, Combinatorics, Number Theory

Solution

Problem Understanding

The problem asks us to determine how many ways we can choose exactly one number from each row of a given m x n matrix such that the greatest common divisor (GCD) of all chosen numbers is 1. In other words, we need to count all valid combinations of one element per row where the combination is coprime as a set.

The input mat is a 2D array of positive integers, with the following constraints: 1 <= mat[i][j] <= 150, 1 <= m, n <= 150. The moderate size of the matrix (up to 150x150) rules out brute-force enumeration of all possible combinations, since the total number of combinations is n^m, which could reach astronomically high values (150^150). The expected output is a single integer representing the number of valid coprime selections, modulo 10^9 + 7.

Important edge cases include matrices where all numbers are the same (GCD is always that number), matrices containing the number 1 (which can help achieve GCD 1), and single-row or single-column matrices. The problem guarantees positive integers, so we do not need to handle zeros.

Approaches

Brute Force

The brute-force approach would enumerate every combination of one element from each row, compute the GCD of the selected numbers, and count those with GCD 1. While this approach is correct, it is computationally infeasible because it requires iterating through n^m combinations, which is far beyond reasonable limits for m, n <= 150.

Optimal Approach

The key insight is to use dynamic programming with memoization, leveraging the fact that the GCD operation is associative. Instead of computing GCDs from scratch for every combination, we can maintain a dictionary (or map) that tracks how many ways we can achieve each possible GCD at each row.

We iterate row by row, and for each number in the row, we update the current GCD counts by combining the existing GCDs with the number using the formula gcd(current_gcd, number). After processing all rows, the count of ways to achieve GCD 1 is simply the value in the dictionary corresponding to key 1. This approach significantly reduces redundant computations and keeps time complexity manageable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^m * m)	O(1)	Enumerates all possible combinations and computes GCDs
Optimal	O(m * n * max_val)	O(max_val)	Uses DP to track number of ways to achieve each GCD, with `max_val=150`

Algorithm Walkthrough

Initialize a dictionary dp that will store the number of ways to achieve each GCD at the current row. Start with dp[0] = 1 or an empty dictionary that will be filled in with the first row.
Iterate over each row in the matrix.
For each number in the current row, iterate over all existing GCDs in dp from the previous row.
For each existing GCD, compute a new GCD using gcd(existing_gcd, number).
Update a new dictionary next_dp by adding the count of the old GCD to the count of the new GCD in next_dp.
After processing all numbers in the row, replace dp with next_dp.
After processing all rows, dp[1] will contain the number of ways to select numbers with GCD 1. Return dp[1] % (10^9 + 7).

Why it works: The algorithm correctly maintains all possible GCDs at each step, ensuring no valid combination is missed. Because GCD is associative, combining new numbers with previous GCDs guarantees that we accurately compute the GCD of any combination of chosen numbers.

Python Solution

from math import gcd
from typing import List
from collections import defaultdict

class Solution:
    def countCoprime(self, mat: List[List[int]]) -> int:
        MOD = 10**9 + 7
        dp = defaultdict(int)
        dp[0] = 1  # Start with "no number chosen"

        for row in mat:
            next_dp = defaultdict(int)
            for num in row:
                for g, count in dp.items():
                    new_gcd = gcd(g, num)
                    next_dp[new_gcd] = (next_dp[new_gcd] + count) % MOD
            dp = next_dp

        return dp[1] if 1 in dp else 0

This implementation starts with an initial "dummy" GCD of 0 representing no numbers chosen. For each number in each row, it calculates the new GCD with all previous GCDs and updates the count of ways to achieve that GCD. The modulo operation ensures that large counts do not overflow.

Go Solution

package main

import (
	"fmt"
)

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

func countCoprime(mat [][]int) int {
	const MOD = 1_000_000_007
	dp := map[int]int{0: 1} // initial "no number chosen"

	for _, row := range mat {
		nextDP := make(map[int]int)
		for _, num := range row {
			for g, count := range dp {
				newGCD := gcd(g, num)
				nextDP[newGCD] = (nextDP[newGCD] + count) % MOD
			}
		}
		dp = nextDP
	}

	return dp[1]
}

In Go, we use a map[int]int for dynamic programming. The GCD function is implemented iteratively. The approach mirrors the Python solution but uses Go syntax and idioms such as range loops over maps.

Worked Examples

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

Initial dp: {0:1}

Row 1 (1,2):

num = 1: gcd(0,1)=1 → next_dp[1]=1
num = 2: gcd(0,2)=2 → next_dp[2]=1

dp after row 1: {1:1, 2:1}

Row 2 (3,4):

num = 3: gcd(1,3)=1 → next_dp[1]+=1 → 1+1=2; gcd(2,3)=1 → next_dp[1]+=1 → 3
num = 4: gcd(1,4)=1 → next_dp[1]+=2 → 5; gcd(2,4)=2 → next_dp[2]=1

dp after row 2: {1:3, 2:1}

Return dp[1]=3

Example 2: mat = [[2,2],[2,2]]

Initial dp: {0:1}

Row 1 (2,2):

gcd(0,2)=2 → next_dp[2]=1+1=2

dp after row 1: {2:2}

Row 2 (2,2):

gcd(2,2)=2 → next_dp[2]=2+2=4

dp after row 2: {2:4}

Return dp[1]=0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n * max_val)	We iterate over m rows, n elements per row, and at most `max_val` distinct GCDs (up to 150)
Space	O(max_val)	We store counts of at most `max_val` different GCDs at any row

The algorithm is efficient because max_val is bounded by 150, keeping the DP dictionary small, even for large matrices.

Test Cases

# Provided examples
assert Solution().countCoprime([[1,2],[3,4]]) == 3  # Example 1
assert Solution().countCoprime([[2,2],[2,2]]) == 0  # Example 2

# Edge cases
assert Solution().countCoprime([[1]]) == 1  # Single element 1
assert Solution().countCoprime([[2]]) == 0  # Single element not 1
assert Solution().countCoprime([[1,2,3],[2,3,4]]) == 11  # Multiple coprime options
assert Solution().countCoprime([[150]*150]*150) == 0  # Large matrix with same non-1 number
assert Solution().countCoprime([[1]*150]*150) == 1  # Large matrix with all 1s

Test	Why
[[1,2],[3,4]]	Checks normal behavior with multiple coprime combinations
[[2,2],[2,2]]	Checks case where no combination yields GCD 1
[[1]]	Checks minimal matrix with 1
[[2]]	Checks minimal matrix without 1
[[1,2,3],[2,3,4]]	Multiple rows with overlapping coprime numbers
[[150]150]150	Stress test with large non-coprime matrix
[[1]150]150	Stress test with large matrix of all