Count Ways to Choose Coprime Integers from Rows - Solution & Explanation

Problem Overview: You are given a matrix where each row contains several integers. Choose exactly one number from every row so that all selected numbers are pairwise coprime. The task is to count how many valid selections exist.

Approach 1: Brute Force Backtracking (Exponential Time, O(n^m))

The most direct strategy is to try every possible combination by picking one element from each row using recursion or backtracking. Maintain the current set of chosen numbers and verify that every new candidate keeps the set coprime by computing gcd(a, b). If the number conflicts with any previously selected value, skip it. This approach clearly demonstrates the constraint but becomes infeasible when rows or columns grow because the search space multiplies quickly. Time complexity is O(n^m) where m is the number of rows and n is the average row size, with O(m) auxiliary space for recursion.

Approach 2: Prime Factor Mask + Dynamic Programming (O(m * n * 2^k))

A better strategy comes from the number theory observation that two numbers are coprime when they share no common prime factor. Precompute the prime factorization of each number and encode it as a bitmask representing the primes it contains. While iterating through rows, maintain a DP state where mask represents the set of prime factors already used by previously chosen numbers.

For each row, try every value in that row. If the value’s prime mask does not intersect with the current mask (mask & valueMask == 0), it can be chosen safely. Transition to the next state by combining masks (mask | valueMask) and accumulate the number of ways. This converts the pairwise coprime constraint into a fast bitmask compatibility check. The complexity becomes O(m * n * 2^k), where k is the number of relevant primes (typically small), and space complexity is O(2^k).

Approach 3: Optimized DP with Precomputed Masks and Rolling States (O(m * n * 2^k))

The DP can be optimized further by compressing states between rows. Instead of storing a full 2D table, keep only the current mask counts and build the next row’s states using a temporary map or array. Precomputing prime masks once for all matrix values avoids repeated factorization. This reduces constant factors while preserving the same asymptotic complexity. The technique is common in problems mixing dynamic programming, bitmask state compression, and number theory.

Recommended for interviews: Start by describing the brute force search to show you understand the constraint. Then move to the prime-factor mask idea, which transforms coprime checking into a constant-time bit operation. Interviewers typically expect the DP with bitmask solution because it combines mathematical insight with efficient state transitions.