3336. Find the Number of Subsequences With Equal GCD LeetCode Solution
In this guide, you will get 3336. Find the Number of Subsequences With Equal GCD LeetCode Solution with the best time and space complexity. The solution to Find the Number of Subsequences With Equal GCD problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Number of Subsequences With Equal GCD
You are given an integer array nums.
Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:
The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
The GCD of the elements of seq1 is equal to the GCD of the elements of seq2.
Return the total number of such pairs.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4]
Output: 10
Explanation:
The subsequence pairs which have the GCD of their elements equal to 1 are:
Space Complexity: O(n \cdot \max(\texttt{nums})^2)
3336. Find the Number of Subsequences With Equal GCD LeetCode Solution in C++
class Solution {
public:
int subsequencePairCount(vector<int>& nums) {
const int maxNum = ranges::max(nums);
vector<vector<vector<int>>> mem(
nums.size(),
vector<vector<int>>(maxNum + 1, vector<int>(maxNum + 1, -1)));
return subsequencePairCount(nums, 0, 0, 0, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of disjoint pairs `seq1` and `seq2` of nums[i..n - 1],
// where GCD(seq1) == x and GCD(seq2) == y.
int subsequencePairCount(const vector<int>& nums, int i, int x, int y,
vector<vector<vector<int>>>& mem) {
if (i == nums.size())
return x > 0 && x == y;
if (mem[i][x][y] != -1)
return mem[i][x][y];
// 1. Skip nums[i].
const int skip = subsequencePairCount(nums, i + 1, x, y, mem);
// 2. Pick nums[i] in the first subsequence.
const int take1 =
subsequencePairCount(nums, i + 1, gcd(x, nums[i]), y, mem);
// 3. Pick nums[i] in the second subsequence.
const int take2 =
subsequencePairCount(nums, i + 1, x, gcd(y, nums[i]), mem);
return mem[i][x][y] = (static_cast<long>(skip) + take1 + take2) % kMod;
}
}; /* code provided by PROGIEZ */
3336. Find the Number of Subsequences With Equal GCD LeetCode Solution in Java
class Solution {
public int subsequencePairCount(int[] nums) {
final int maxNum = Arrays.stream(nums).max().getAsInt();
Integer[][][] mem = new Integer[nums.length][maxNum + 1][maxNum + 1];
return subsequencePairCount(nums, 0, 0, 0, mem);
}
private static final int kMod = 1_000_000_007;
private int subsequencePairCount(int[] nums, int i, int x, int y, Integer[][][] mem) {
if (i == nums.length)
return (x > 0 && x == y) ? 1 : 0;
if (mem[i][x][y] != null)
return mem[i][x][y];
// 1. Skip nums[i]
final int skip = subsequencePairCount(nums, i + 1, x, y, mem);
// 2. Pick nums[i] in the first subsequence
final int take1 = subsequencePairCount(nums, i + 1, gcd(x, nums[i]), y, mem);
// 3. Pick nums[i] in the second subsequence
final int take2 = subsequencePairCount(nums, i + 1, x, gcd(y, nums[i]), mem);
return mem[i][x][y] = (int) (((long) skip + take1 + take2) % kMod);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
3336. Find the Number of Subsequences With Equal GCD LeetCode Solution in Python
class Solution:
def subsequencePairCount(self, nums: list[int]) -> int:
kMod = 1_000_000_007
@functools.lru_cache(None)
def dp(i: int, x: int, y: int) -> int:
if i == len(nums):
return int(x > 0 and x == y)
# 1. Skip nums[i]
skip = dp(i + 1, x, y)
# 2. Pick nums[i] in the first subsequence
take1 = dp(i + 1, math.gcd(x, nums[i]), y)
# 3. Pick nums[i] in the second subsequence
take2 = dp(i + 1, x, math.gcd(y, nums[i]))
return (skip + take1 + take2) % kMod
return dp(0, 0, 0) # code by PROGIEZ
