LeetCode 3336: Find the Number of Subsequences With Equal GCD Solution
Master LeetCode problem 3336 (Find the Number of Subsequences With Equal GCD), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
3336. Find the Number of Subsequences With Equal GCD
Problem Explanation
Explanation
To solve this problem, we can iterate through all possible divisors of each number in the array nums. For each divisor, we can calculate the contribution of subsequences with GCD equal to that divisor. We can use dynamic programming to keep track of the number of subsequences having a certain GCD. Finally, we can sum up the contributions for all divisors to get the total number of pairs of subsequences with equal GCD.
- Initialize a map to store the count of subsequences with a specific GCD.
- Iterate through each number in the array
nums. - For each number, iterate through all divisors of that number.
- For each divisor, update the count of subsequences with that GCD based on the current number.
- Finally, sum up the contributions for all divisors to get the total count of pairs of subsequences with equal GCD.
Time Complexity: O(n * sqrt(max(nums))) where n is the length of nums and max(nums) is the maximum number in nums.
Space Complexity: O(n)
Solution Code
class Solution {
public int countSubsequences(int[] nums) {
int MOD = 1000000007;
int n = nums.length;
int[] dp = new int[201];
dp[0] = 1;
for (int num : nums) {
int[] dpNew = Arrays.copyOf(dp, dp.length);
for (int i = 0; i < dp.length; i++) {
if (dp[i] > 0) {
int gcd = gcd(i, num);
dpNew[gcd] = (dpNew[gcd] + dp[i]) % MOD;
}
}
dp = dpNew;
dp[num] = (dp[num] + 1) % MOD;
}
long res = 0;
for (int i = 1; i < dp.length; i++) {
res = (res + dp[i]) % MOD;
}
return (int) res;
}
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 3336 (Find the Number of Subsequences With Equal GCD)?
This page provides optimized solutions for LeetCode problem 3336 (Find the Number of Subsequences With Equal GCD) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 3336 (Find the Number of Subsequences With Equal GCD)?
The time complexity for LeetCode 3336 (Find the Number of Subsequences With Equal GCD) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 3336 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3336 in Java, C++, or Python.