21. Count the Coprimes

✅ GFG solution to the Count the Coprimes problem: count pairs with GCD=1 using Möbius function and inclusion-exclusion principle for efficient computation. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given an array arr[] of positive integers. Your task is to count the number of pairs (i, j) such that:

0 ≤ i < j ≤ n-1
gcd(arr[i], arr[j]) = 1

In other words, count the number of unordered pairs of indices (i, j) where the elements at those positions are co-prime (their greatest common divisor is 1).

📘 Examples

Example 1

Input: arr[] = [1, 2, 3]
Output: 3
Explanation: (0,1), (0,2), (1,2) are the pair of indices where gcd(arr[i], arr[j]) = 1

Example 2

Input: arr[] = [4, 8, 3, 9]
Output: 4
Explanation: (0,2), (0,3), (1,2), (1,3) are the pair of indices where gcd(arr[i], arr[j]) = 1

🔒 Constraints

$2 \le \text{arr.size()} \le 10^4$
$1 \le \text{arr}[i] \le 10^4$

✅ My Approach

The optimal approach uses the Möbius Function with Inclusion-Exclusion Principle to efficiently count coprime pairs without checking every pair individually:

Möbius Function + Inclusion-Exclusion

Core Insight:
- Instead of checking all pairs individually (O(n²) with GCD computation), we use number theory.
- Count pairs with specific GCD values using inclusion-exclusion principle.
- Möbius function helps eliminate overcounting in inclusion-exclusion.
Algorithm Steps:
- Step 1: Find maximum element and create frequency array cnt[].
- Step 2: Compute Möbius function mu[] using sieve method.
- Step 3: For each divisor d, count how many elements are divisible by d (store in div[]).
- Step 4: Apply inclusion-exclusion: pairs with GCD=1 = total pairs - pairs with GCD>1.
- Step 5: Use Möbius function to compute the final result efficiently.
Möbius Function Properties:
- μ(1) = 1
- μ(n) = 0 if n has squared prime factor
- μ(n) = (-1)^k if n is product of k distinct primes
- Used to invert inclusion-exclusion formulas
Mathematical Formula:
- For each divisor d: if mu[d] ≠ 0 and div[d] > 1
- Add mu[d] * div[d] * (div[d] - 1) / 2 to result
- This counts pairs where GCD is exactly 1 using inclusion-exclusion

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n log n), where n is the maximum element in array. The first term is for sieve-based Möbius computation, and the second term is for divisor counting across all elements.
Expected Auxiliary Space Complexity: O(n), where n is the maximum element. We need arrays for frequency counting, divisor sums, Möbius function values, and visited markers during sieve computation.

🧑‍💻 Code (C++)

class Solution {
public:
    int cntCoprime(vector<int>& arr) {
        int mx = *max_element(arr.begin(), arr.end());
        vector<int> cnt(mx + 1), div(mx + 1), mu(mx + 1, 1);
        vector<bool> vis(mx + 1);
        
        for (int x : arr) cnt[x]++;

        for (int i = 1; i <= mx; ++i)
            for (int j = i; j <= mx; j += i)
                div[i] += cnt[j];

        for (int i = 2; i <= mx; ++i) {
            if (!vis[i]) {
                for (int j = i; j <= mx; j += i) {
                    mu[j] *= -1;
                    vis[j] = 1;
                }
                for (long long j = (long long)i * i; j <= mx; j += (long long)i * i)
                    mu[j] = 0;
            }
        }

        int ans = 0;
        for (int i = 1; i <= mx; ++i)
            if (mu[i] && div[i] > 1)
                ans += mu[i] * div[i] * (div[i] - 1) / 2;
        
        return ans;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Sieve-Based Möbius with Early Termination

💡 Algorithm Steps:

Use sieve to compute Möbius function efficiently
Early termination when divisor count < 2
Optimized prime factorization
Single-pass frequency and divisor counting

class Solution {
public:
    int cntCoprime(vector<int>& arr) {
        int n = *max_element(arr.begin(), arr.end());
        vector<int> f(n + 1), d(n + 1), mu(n + 1, 1);
        vector<bool> vis(n + 1);
        
        for (int x : arr) f[x]++;
        
        for (int i = 2; i <= n; ++i) {
            if (!vis[i]) {
                for (int j = i; j <= n; j += i) {
                    mu[j] *= -1;
                    vis[j] = 1;
                }
                for (long long j = (long long)i * i; j <= n; j += (long long)i * i)
                    mu[j] = 0;
            }
        }
        
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; j += i)
                d[i] += f[j];
        
        int res = 0;
        for (int i = 1; i <= n; ++i)
            if (mu[i] && d[i] > 1)
                res += mu[i] * d[i] * (d[i] - 1) / 2;
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n log n)
Auxiliary Space: 💾 O(n) - for arrays

✅ Why This Approach?

Sieve-based prime detection
Efficient Möbius computation
Early termination optimizations

📊 3️⃣ GCD-Based Direct Counting

💡 Algorithm Steps:

Use inclusion-exclusion principle
Count pairs with specific GCD values
Direct frequency-based computation
Optimized divisor iteration

class Solution {
public:
    int cntCoprime(vector<int>& arr) {
        int mx = *max_element(arr.begin(), arr.end());
        vector<int> freq(mx + 1), cnt(mx + 1);
        
        for (int x : arr) freq[x]++;
        
        for (int g = 1; g <= mx; ++g) {
            for (int mul = g; mul <= mx; mul += g)
                cnt[g] += freq[mul];
        }
        
        vector<int> coprime(mx + 1);
        for (int g = mx; g >= 1; --g) {
            coprime[g] = cnt[g] * (cnt[g] - 1) / 2;
            for (int mul = g + g; mul <= mx; mul += g)
                coprime[g] -= coprime[mul];
        }
        
        return coprime[1];
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n log n)
Auxiliary Space: 💾 O(n) - for frequency arrays

✅ Why This Approach?

Direct GCD-based computation
Bottom-up inclusion-exclusion
No Möbius function needed

📊 4️⃣ Optimized Divisor Sum Approach

💡 Algorithm Steps:

Precompute smallest prime factors
Fast Möbius function calculation
Efficient divisor counting
Single-pass result computation

class Solution {
public:
    int cntCoprime(vector<int>& arr) {
        int n = *max_element(arr.begin(), arr.end());
        vector<int> spf(n + 1), f(n + 1), d(n + 1);
        
        iota(spf.begin(), spf.end(), 0);
        for (int i = 2; i * i <= n; ++i)
            if (spf[i] == i)
                for (int j = i * i; j <= n; j += i)
                    if (spf[j] == j) spf[j] = i;
        
        for (int x : arr) f[x]++;
        
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; j += i)
                d[i] += f[j];
        
        auto mobius = [&](int x) {
            int res = 1, prev = -1;
            while (x > 1) {
                int p = spf[x], cnt = 0;
                while (x % p == 0) x /= p, cnt++;
                if (cnt > 1) return 0;
                res *= -1;
            }
            return res;
        };
        
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (d[i] > 1) {
                int mu = mobius(i);
                if (mu) ans += mu * d[i] * (d[i] - 1) / 2;
            }
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n log log n + n log n)
Auxiliary Space: 💾 O(n) - for SPF and arrays

✅ Why This Approach?

SPF-based factorization
On-demand Möbius calculation
Memory-efficient implementation

📊 5️⃣ Brute Force Approach (For Reference)

💡 Algorithm Steps:

Check every pair (i, j) where i < j
Compute GCD of arr[i] and arr[j]
Count pairs where GCD equals 1
Simple but inefficient for large inputs

class Solution {
public:
    int cntCoprime(vector<int>& arr) {
        int n = arr.size();
        int count = 0;
        
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (__gcd(arr[i], arr[j]) == 1) {
                    count++;
                }
            }
        }
        return count;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n² log(max_element))
Auxiliary Space: 💾 O(1)

✅ Why This Approach?

Simple and intuitive
Easy to understand and implement
Good for small inputs or educational purposes

Note: This approach results in Time Limit Exceeded (TLE) for large inputs (fails ~1010/1120 test cases due to time constraints).

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🔍 Optimized Möbius

🟢 O(n log n)

🟡 O(n)

🚀 Fastest for large inputs

💾 Multiple array allocations

🔺 Sieve-Based Möbius

🟢 O(n log n)

🟡 O(n)

🔧 Better prime detection

💾 Additional boolean array

⏰ GCD-Based Direct

🟢 O(n log n)

🟡 O(n)

🚀 No Möbius function needed

🔄 Backward iteration required

📊 SPF Divisor Sum

🟢 O(n log log n + n log n)

🟡 O(n)

⚡ On-demand calculations

🔧 Complex factorization logic

🐌 Brute Force (TLE)

🔴 O(n² log(max))

🟢 O(1)

🔧 Simple to understand

⏰ Too slow for large inputs

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

⚡ Large arrays, high performance

🥇 Optimized Möbius

★★★★★

📊 Balanced memory usage

🥈 GCD-Based Direct

★★★★☆

🎯 Educational/interview purposes

🥉 Sieve-Based Möbius

★★★★☆

🚀 Competitive programming

🏅 SPF Divisor Sum

★★★★★

📚 Small inputs, learning

🎖️ Brute Force (TLE)

★★☆☆☆

🧑‍💻 Code (Java)

class Solution {
    int cntCoprime(int[] arr) {
        int mx = Arrays.stream(arr).max().orElse(0);
        int[] cnt = new int[mx + 1], div = new int[mx + 1], mu = new int[mx + 1];
        boolean[] vis = new boolean[mx + 1];
        
        for (int x : arr) cnt[x]++;
        
        Arrays.fill(mu, 1);
        for (int i = 2; i <= mx; ++i) {
            if (!vis[i]) {
                for (int j = i; j <= mx; j += i) {
                    mu[j] *= -1;
                    vis[j] = true;
                }
                for (long j = (long)i * i; j <= mx; j += (long)i * i)
                    mu[(int)j] = 0;
            }
        }
        
        for (int i = 1; i <= mx; ++i)
            for (int j = i; j <= mx; j += i)
                div[i] += cnt[j];
        
        int ans = 0;
        for (int i = 1; i <= mx; ++i)
            if (mu[i] != 0 && div[i] > 1)
                ans += mu[i] * div[i] * (div[i] - 1) / 2;
        
        return ans;
    }
}

🐍 Code (Python)

class Solution:
    def cntCoprime(self, arr):
        mx = max(arr)
        cnt, div, mu = [0] * (mx + 1), [0] * (mx + 1), [1] * (mx + 1)
        vis = [False] * (mx + 1)
        
        for x in arr:
            cnt[x] += 1
        
        for i in range(2, mx + 1):
            if not vis[i]:
                for j in range(i, mx + 1, i):
                    mu[j] *= -1
                    vis[j] = True
                for j in range(i * i, mx + 1, i * i):
                    mu[j] = 0
        
        for i in range(1, mx + 1):
            for j in range(i, mx + 1, i):
                div[i] += cnt[j]
        
        ans = 0
        for i in range(1, mx + 1):
            if mu[i] and div[i] > 1:
                ans += mu[i] * div[i] * (div[i] - 1) // 2
        
        return ans

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous20. Count Numbers Containing Specific Digits Next22. Smallest Positive Missing

Last updated 6 months ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagMöbius Function + Inclusion-Exclusion

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Sieve-Based Möbius with Early Termination

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ GCD-Based Direct Counting

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Optimized Divisor Sum Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 5️⃣ Brute Force Approach (For Reference)

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag🧑‍💻 Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

🔒 Constraints

✅ My Approach

Möbius Function + Inclusion-Exclusion

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Sieve-Based Möbius with Early Termination

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ GCD-Based Direct Counting

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Optimized Divisor Sum Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 5️⃣ Brute Force Approach (For Reference)

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

🧑‍💻 Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count