Is Count Ways to Choose Coprime Integers from Rows easy or hard?

Count Ways to Choose Coprime Integers from Rows is classified as a Hard problem. It requires understanding number theory (prime factorization), dynamic programming, and bitmask state compression to efficiently enforce the pairwise coprime constraint.

Count Ways to Choose Coprime Integers from Rows Python/Java solution

Implementations typically precompute prime masks for each matrix value, then iterate row by row updating DP states. Python often uses dictionaries or arrays for mask counts, while Java and C++ commonly use integer arrays for faster transitions. The same bitmask DP logic applies across all languages.

How to solve Count Ways to Choose Coprime Integers from Rows in O(n)?

A pure O(n) solution is not typical because the problem requires exploring combinations across rows. The practical optimal solution uses dynamic programming with bitmask state compression. By representing prime factors as bitmasks and updating DP states row by row, the algorithm avoids exponential combination checks while keeping complexity manageable.

What is the best approach for Count Ways to Choose Coprime Integers from Rows?

The most efficient approach uses prime factorization with dynamic programming over bitmasks. Each number is converted into a mask representing its prime factors, and a DP state tracks which primes are already used by previously selected numbers. A number can be chosen only if its mask does not overlap with the current mask. This reduces coprime checks to constant-time bit operations.

Is Count Ways to Choose Coprime Integers from Rows asked at Google/Amazon/Meta?

Problems combining coprime constraints, dynamic programming, and bitmask optimization appear frequently in interviews at large tech companies. Variants involving prime factor masks, subset DP, or coprime selection are common in Google and Meta interview preparation sets.

What data structure is used in Count Ways to Choose Coprime Integers from Rows?

The solution mainly relies on arrays or hash maps for dynamic programming states and bitmasks to encode prime factors. Precomputed prime factorizations allow fast compatibility checks using bitwise AND operations.

What is the time complexity of Count Ways to Choose Coprime Integers from Rows?

The optimal dynamic programming approach runs in O(m * n * 2^k) time, where m is the number of rows, n is the average number of values per row, and k is the number of distinct primes considered. Space complexity is O(2^k) for storing DP states representing used prime factors.

Description Hints 5 Video 20:16

3725. Count Ways to Choose Coprime Integers from Rows

Hard46.8% acceptance

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

Topics

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

Use dp[row][g], where row is the current row and g is the current gcd value.

Hint 3

Initialize the first row: for each value v in row 0 do dp[0][v] += 1.

Hint 4

For a row i, use the values from the previous row i - 1 to build the values: for each previous gcd g and each value v in row i.

Hint 5

The final answer is dp[n-1][1] (number of ways with gcd 1).

LanguageLoading editor…

1class Solution:
2    def countCoprime(self, mat: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

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

Your code is saved on this device.