What is the time complexity of Find the Number of Subsequences With Equal GCD?

The optimal solution has a time complexity of O(MAX_VAL^3).

What is the space complexity of Find the Number of Subsequences With Equal GCD?

The space complexity is O(MAX_VAL).

What data structures are used to solve Find the Number of Subsequences With Equal GCD?

This problem uses Array, Math, Dynamic Programming, Number Theory. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Find the Number of Subsequences With Equal GCD?

Insight 1: Precompute the Möbius function (mu) to efficiently calculate inclusion-exclusion. Insight 2: Iterate through possible GCD values from 1 to MAX_VAL (200), and for each possible GCD 'g', consider only numbers in the input array that are multiples of 'g'.

Which companies ask LeetCode 3336. Find the Number of Subsequences With Equal GCD in interviews?

This problem is frequently asked at Infosys.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find the Number of Subsequences With Equal GCD - LeetCode 3336 Solution

Find the Number of Subsequences With Equal GCD - Complete Solution Guide

Find the Number of Subsequences With Equal GCD is LeetCode problem 3336, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 10 9 + 7 . Example 1: Input: nums = [1,2,3,4] Output: 10 Explanation:

Detailed Explanation

The problem asks us to find the number of pairs of non-empty, disjoint subsequences from a given array `nums` such that the greatest common divisor (GCD) of the elements in the first subsequence is equal to the GCD of the elements in the second subsequence. The subsequences must be disjoint, meaning they cannot share any indices from the original `nums` array. We need to return the count of these pairs modulo 10^9 + 7.

Solution Approach

The solution uses the Möbius inversion formula to calculate the number of disjoint subsequence pairs with equal GCDs. It iterates through all possible GCD values from 1 to 200. For each GCD `g`, it identifies elements in `nums` that are multiples of `g`. Then, it employs the Möbius function and inclusion-exclusion to count the number of such pairs. The Möbius function is precomputed to optimize the calculation. The disjoint subsequences requirement adds complexity, leading to the power of 3 and power of 2 calculations within the inclusion-exclusion part.

Step-by-Step Algorithm

Step 1: Precompute the Möbius function (mu) for all values from 1 to MAX_VAL. This is done using the sieve method.
Step 2: Iterate through each possible GCD value `g` from 1 to MAX_VAL.
Step 3: For each `g`, create a map `T_freq` that stores the frequency of `j/g` for all elements `j` in `nums` that are multiples of `g`.
Step 4: Create an array `count_multiples_t` such that `count_multiples_t[m]` stores the count of elements in `T_freq` which are multiples of `m`.
Step 5: Calculate the contribution of the current GCD `g` to the final answer using inclusion-exclusion. Iterate through all possible divisors d1 and d2 of elements in T_freq and calculate C_T.
Step 6: Accumulate the contributions from each GCD value `g` into `total_pairs`.
Step 7: Return `total_pairs` modulo 10^9 + 7.

Key Insights

Insight 1: Precompute the Möbius function (mu) to efficiently calculate inclusion-exclusion.
Insight 2: Iterate through possible GCD values from 1 to MAX_VAL (200), and for each possible GCD 'g', consider only numbers in the input array that are multiples of 'g'.
Insight 3: For a given GCD 'g', the count of subsequences with GCD 'g' can be determined using inclusion-exclusion principle and the Möbius function.

Complexity Analysis

Time Complexity: O(MAX_VAL^3)

Space Complexity: O(MAX_VAL)

Topics

This problem involves: Array, Math, Dynamic Programming, Number Theory.

Companies

Asked at: Infosys.

Find the Number of Subsequences With Equal GCD | LeetCode 3336

Hard

Array Math Dynamic Programming Number Theory

Time: O(MAX_VAL^3)Space: O(MAX_VAL)

Solution Code

Available in:

import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subsequencePairCount(int[] nums) {
        int MOD = (int)1e9 + 7;
        int MAX_VAL = 200;

        int[] mu = new int[MAX_VAL + 1];
        int[] lp = new int[MAX_VAL + 1];
        List<Integer> primes = new ArrayList<>();
        mu[1] = 1;

        for (int i = 2; i <= MAX_VAL; i++) {
            if (lp[i] == 0) {
                lp[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            for (int p : primes) {
                if (p > lp[i] || i * p > MAX_VAL) {
                    break;
                }
                lp[i * p] = p;
                if (p == lp[i]) {
                    mu[i * p] = 0;
                } else {
                    mu[i * p] = -mu[i];
                }
            }
        }

        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        long total_pairs = 0;

        for (int g = 1; g <= MAX_VAL; g++) {
            Map<Integer, Integer> T_freq = new HashMap<>();
            int max_t = 0;
            for (int j = g; j <= MAX_VAL; j += g) {
                if (freq.containsKey(j) && freq.get(j) > 0) {
                    int val = j / g;
                    T_freq.put(val, freq.get(j));
                    max_t = Math.max(max_t, val);
                }
            }

            if (T_freq.isEmpty()) {
                continue;
            }

            int[] count_multiples_t = new int[max_t + 1];
            for (int m = 1; m <= max_t; m++) {
                for (int j = m; j <= max_t; j += m) {
                    if (T_freq.containsKey(j)) {
                        count_multiples_t[m] += T_freq.get(j);
                    }
                }
            }

            long C_T = 0;
            for (int d1 = 1; d1 <= max_t; d1++) {
                int mu1 = mu[d1];
                if (mu1 == 0) {
                    continue;
                }
                for (int d2 = 1; d2 <= max_t; d2++) {
                    int mu2 = mu[d2];
                    if (mu2 == 0) {
                        continue;
                    }

                    int l = (d1 * d2) / gcd(d1, d2);

                    int k1 = count_multiples_t[d1];
                    int k2 = count_multiples_t[d2];
                    int k12 = 0;
                    if (l <= max_t) {
                        k12 = count_multiples_t[l];
                    }

                    long term_val_part1 = power(3, k12, MOD);
                    long term_val_part2 = power(2, k1 - k12, MOD);
                    long term_val_part3 = power(2, k2 - k12, MOD);

                    long term_val = (term_val_part1 * term_val_part2) % MOD;
                    term_val = (term_val * term_val_part3) % MOD;

                    term_val = (term_val - power(2, k1, MOD) + MOD) % MOD;
                    term_val = (term_val - power(2, k2, MOD) + MOD) % MOD;
                    term_val = (term_val + 1) % MOD;

                    if (mu1 * mu2 == 1) {
                        C_T = (C_T + term_val) % MOD;
                    } else {
                        C_T = (C_T - term_val + MOD) % MOD;
                    }
                }
            }

            total_pairs = (total_pairs + C_T) % MOD;
        }

        return (int)total_pairs;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3336: Find the Number of Subsequences With Equal GCD - Detailed explanation and solution approaches.

Topics

Array Math Dynamic Programming Number Theory

Companies

Infosys

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:3336

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Precompute the Möbius function (mu) for all values from 1 to MAX_VAL. This is done using the sieve method.
2
Step 2: Iterate through each possible GCD value `g` from 1 to MAX_VAL.
3
Step 3: For each `g`, create a map `T_freq` that stores the frequency of `j/g` for all elements `j` in `nums` that are multiples of `g`.
4
Step 4: Create an array `count_multiples_t` such that `count_multiples_t[m]` stores the count of elements in `T_freq` which are multiples of `m`.
5
Step 5: Calculate the contribution of the current GCD `g` to the final answer using inclusion-exclusion. Iterate through all possible divisors d1 and d2 of elements in T_freq and calculate C_T.
6
Step 6: Accumulate the contributions from each GCD value `g` into `total_pairs`.
7
Step 7: Return `total_pairs` modulo 10^9 + 7.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(MAX_VAL^3)

💾

Space Complexity

O(MAX_VAL)

📝

Why?

The time complexity is dominated by the triple nested loop structure while iterating over all possible values of GCD, divisor d1, and divisor d2. The space complexity arises from the arrays/maps used to store precomputed values and frequencies.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible pairs of disjoint subsequences, calculate the GCD of each subsequence, and count the pairs with equal GCDs. This approach would involve generating all possible subsets of the input array and then filtering those subsets to create disjoint pairs.

Time: O(3^N * N), where N is the length of the input array.Space: O(N), where N is the length of the input array.

Trade-offs: The brute force approach is simple to understand but computationally expensive and only suitable for very small input arrays. The Mobius inversion provides a much more efficient approach. The brute force approach would timeout.

✨

Key Insights

1Insight 1: Precompute the Möbius function (mu) to efficiently calculate inclusion-exclusion.
2Insight 2: Iterate through possible GCD values from 1 to MAX_VAL (200), and for each possible GCD 'g', consider only numbers in the input array that are multiples of 'g'.
3Insight 3: For a given GCD 'g', the count of subsequences with GCD 'g' can be determined using inclusion-exclusion principle and the Möbius function.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Input array with all the same elements. The solution handles this case correctly by counting the number of disjoint subsequence pairs with that common GCD.
Edge case 2: Input array with only one element. The outer loop (iterating through GCDs) ensures that the algorithm correctly counts the possible pairs for each applicable GCD.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the modulo operation correctly, which can lead to incorrect results due to integer overflow.

✗Common mistake 2: Incorrectly applying the inclusion-exclusion principle, leading to inaccurate counts of subsequences.

✗Common mistake 3: Failing to recognize the disjoint subsequence requirement, leading to overcounting.

✗Common mistake 4: Incorrectly calculating the GCD of a subsequence (e.g., returning 0 when the subsequence is empty, which leads to wrong GCD calculations). Although the problem states non-empty subsequences, incorrect implementations of GCD calculations can lead to issues.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: This type of problem, involving number theory and combinatorics, can be applied in cryptography, where modular arithmetic and GCD calculations are fundamental.

🏦Real-world scenario 2: It can also be useful in data analysis for identifying patterns related to common divisors within datasets. Imagine analyzing frequency of events based on specific time periods, where finding common periods can become relevant to the type of analysis used in this problem.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 5, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Find the Number of Subsequences With Equal GCD"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?