Count of non co-prime pairs from the range [1, arr[i]] for every array element

Given an array arr[] consisting of  N integers, the task for every i^th element of the array is to find the number of non co-prime pairs from the range [1, arr[i]].

Examples:

Input: N = 2, arr[] = {3, 4}
Output: 2 4
Explanation:

1. All non-co-prime pairs from the range [1, 3] are (2, 2) and (3, 3).
2. All non-co-prime pairs from the range [1, 4] are (2, 2), (2, 4), (3, 3) and (4, 4).

Input: N = 3, arr[] = {5, 10, 20}
Output: 5 23 82

Naive Approach: The simplest approach to solve the problem is to iterate over every i^th array element and then, generate every possible pair from the range [1, arr[i]], and for every pair, check whether it is non-co-prime, i.e. gcd of the pair is greater than 1 or not.
Follow the steps below to solve this problem:

• Iterate over the range [0, N – 1] using a variable, say i, and perform the following steps: 
  • Initialize variables lastEle as arr[i] and count as 0 to store the last value of the current range and number of co-prime pairs respectively.
  • Iterate over every pair from the range [1, arr[i]] using variables x and y and do the following:
    • If GCD(x, y) is greater than 1, then the increment count by 1.
  • Finally, print the count as the answer.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int gcd(int a, int b) {     if (b == 0)         return a;        return gcd(b, a % b); }    void countPairs(int* arr, int N) {             for (int i = 0; i < N; i++) {                              int count = 0;                     for (int x = 1; x <= arr[i]; x++) {                             for (int y = x; y <= arr[i]; y++) {                                                      if (gcd(x, y) > 1)                     count++;             }         }         cout << count << " ";     } }    int main() {          int arr[] = { 5, 10, 20 };     int N = 3;             countPairs(arr, N);        return 0; }

Output

5 23 82 

Time Complexity: O(N*M²*log(M)), where M is the maximum element of the array.
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by using Euler’s totient function, and prefix sum array. Follow the steps below to solve the problem:

• Initialize two arrays, say phi[] and ans[] as 0, where the i^th element of the array represents the count of integers that is coprime to i and the count of non-coprime pairs formed from the range [1, arr[i]].
• Iterate over the range [1, MAX] using a variable, say i, and assign i to phi[i].
• Iterate over the range [2, MAX] using a variable, say i,  and perform the following steps:
  • If phi[i] = i, then iterate over the range [i, MAX] using a variable j and perform the following steps:
    • Decrement phi[j] / i from phi[j] and then increment j by i.
• Iterate over the range [1, MAX] using a variable, say i,  and perform the following steps:
  • Update ans[i] to ans[i – 1] + (i – phi[i]).
• Finally, after completing the above steps, print the array ans[].

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std; const int MAX = 1005;    void preCalculate(vector<int>& phi,                   vector<int>& ans) {     phi[0] = 0;     phi[1] = 1;             for (int i = 2; i <= MAX; i++)         phi[i] = i;             for (int i = 2; i <= MAX; i++) {                     if (phi[i] == i) {                for (int j = i; j <= MAX; j += i)                                                                       phi[j] -= (phi[j] / i);         }     }             for (int i = 1; i <= MAX; i++)         ans[i] = ans[i - 1] + (i - phi[i]); }    void countPairs(int* arr, int N) {                    vector<int> phi(1e5, 0);             vector<int> ans(1e5, 0);             preCalculate(phi, ans);             for (int i = 0; i < N; ++i) {         cout << ans[arr[i]] << " ";     } }    int main() {          int arr[] = { 5, 10, 20 };     int N = 3;             countPairs(arr, N); }

Output

5 23 82 

Time Complexity: O(N+ M*log(N)), where M is the maximum element of the array.
Auxiliary Space: O(M+N)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets