Given an array arr[] consisting of N integers, the task for every ith 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:
- All non-co-prime pairs from the range [1, 3] are (2, 2) and (3, 3).
- 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 ith 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++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Recursive function to // return gcd of two numbers int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count the number of // non co-prime pairs for each query void countPairs( int * arr, int N) { // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Stores the count of // non co-prime pairs int count = 0; // Iterate over the range [1, x] for ( int x = 1; x <= arr[i]; x++) { // Iterate over the range [x, y] for ( int y = x; y <= arr[i]; y++) { // If gcd of current pair // is greater than 1 if (gcd(x, y) > 1) count++; } } cout << count << " " ; } } // Driver Code int main() { // Given Input int arr[] = { 5, 10, 20 }; int N = 3; // Function Call countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Recursive function to // return gcd of two numbers static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to count the number of // non co-prime pairs for each query static void countPairs( int [] arr, int N) { // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Stores the count of // non co-prime pairs int count = 0 ; // Iterate over the range [1, x] for ( int x = 1 ; x <= arr[i]; x++) { // Iterate over the range [x, y] for ( int y = x; y <= arr[i]; y++) { // If gcd of current pair // is greater than 1 if (gcd(x, y) > 1 ) count++; } } System.out.print(count + " " ); } } // Driver Code public static void main(String[] args) { // Given Input int arr[] = { 5 , 10 , 20 }; int N = 3 ; // Function Call countPairs(arr, N); } } // This code is contributed by subhammahato348 |
Python3
# Python3 program for the above approach # Recursive program to # return gcd of two numbers def gcd(a, b): if b = = 0 : return a return gcd(b, a % b) # Function to count the number of # non co-prime pairs for each query def countPairs(arr, N): # Traverse the array arr[] for i in range ( 0 , N): # Stores the count of # non co-prime pairs count = 0 # Iterate over the range [1,x] for x in range ( 1 , arr[i] + 1 ): # Iterate over the range [x,y] for y in range (x, arr[i] + 1 ): # If gcd of current pair # is greater than 1 if gcd(x, y) > 1 : count + = 1 print (count, end = " " ) # Driver code if __name__ = = '__main__' : # Given Input arr = [ 5 , 10 , 20 ] N = len (arr) # Function Call countPairs(arr, N) # This code is contributed by MuskanKalra1 |
C#
// C# program for the above approach using System; class GFG{ // Recursive function to // return gcd of two numbers static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count the number of // non co-prime pairs for each query static void countPairs( int [] arr, int N) { // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Stores the count of // non co-prime pairs int count = 0; // Iterate over the range [1, x] for ( int x = 1; x <= arr[i]; x++) { // Iterate over the range [x, y] for ( int y = x; y <= arr[i]; y++) { // If gcd of current pair // is greater than 1 if (gcd(x, y) > 1) count++; } } Console.Write(count + " " ); } } // Driver Code public static void Main(String[] args) { // Given Input int []arr = { 5, 10, 20 }; int N = 3; // Function Call countPairs(arr, N); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach // Recursive function to // return gcd of two numbers function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count the number of // non co-prime pairs for each query function countPairs(arr, N) { // Traverse the array arr[] for ( var i = 0; i < N; i++) { // Stores the count of // non co-prime pairs var count = 0; // Iterate over the range [1, x] for ( var x = 1; x <= arr[i]; x++) { // Iterate over the range [x, y] for ( var y = x; y <= arr[i]; y++) { // If gcd of current pair // is greater than 1 if (gcd(x, y) > 1) count++; } } document.write(count + " " ); } } // Driver Code // Given Input var arr = [ 5, 10, 20 ]; var N = 3; // Function Call countPairs(arr, N); // This code is contributed by shivanisinghss2110 </script> |
5 23 82
Time Complexity: O(N*M2*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 ith 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.
- If phi[i] = i, then iterate over the range [i, MAX] using a variable j and perform the following steps:
- 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++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MAX = 1005; // Auxiliary function to pre-compute // the answer for each array void preCalculate(vector< int >& phi, vector< int >& ans) { phi[0] = 0; phi[1] = 1; // Iterate over the range [1, MAX] for ( int i = 2; i <= MAX; i++) phi[i] = i; // Iterate over the range [1, MAX] for ( int i = 2; i <= MAX; i++) { // If the number is prime if (phi[i] == i) { for ( int j = i; j <= MAX; j += i) // Subtract the number of // pairs which has i as one // of their factors phi[j] -= (phi[j] / i); } } // Iterate over the range [1, MAX] for ( int i = 1; i <= MAX; i++) ans[i] = ans[i - 1] + (i - phi[i]); } // Function to count the number of // non co-prime pairs for each query void countPairs( int * arr, int N) { // The i-th element stores // the count of element that // are co-prime with i vector< int > phi(1e5, 0); // Stores the resulting array vector< int > ans(1e5, 0); // Function Call preCalculate(phi, ans); // Traverse the array arr[] for ( int i = 0; i < N; ++i) { cout << ans[arr[i]] << " " ; } } // Driver Code int main() { // Given Input int arr[] = { 5, 10, 20 }; int N = 3; // Function Call countPairs(arr, N); } |
Java
// Java program for the above approach import java.util.*; class GFG { static int MAX = 1005 ; // Auxiliary function to pre-compute // the answer for each array static void preCalculate( int [] phi, int [] ans) { phi[ 0 ] = 0 ; phi[ 1 ] = 1 ; // Iterate over the range [1, MAX] for ( int i = 2 ; i <= MAX; i++) phi[i] = i; // Iterate over the range [1, MAX] for ( int i = 2 ; i <= MAX; i++) { // If the number is prime if (phi[i] == i) { for ( int j = i; j <= MAX; j += i) // Subtract the number of // pairs which has i as one // of their factors phi[j] -= (phi[j] / i); } } // Iterate over the range [1, MAX] for ( int i = 1 ; i <= MAX; i++) ans[i] = ans[i - 1 ] + (i - phi[i]); } // Function to count the number of // non co-prime pairs for each query static void countPairs( int [] arr, int N) { // The i-th element stores // the count of element that // are co-prime with i int [] phi = new int [ 100000 ]; Arrays.fill(phi, 0 ); // Stores the resulting array int [] ans = new int [ 100000 ]; Arrays.fill(ans, 0 ); // Function Call preCalculate(phi, ans); // Traverse the array arr[] for ( int i = 0 ; i < N; ++i) { System.out.print(ans[arr[i]] + " " ); } } // Driver Code public static void main(String[] args) { // Given Input int arr[] = { 5 , 10 , 20 }; int N = 3 ; // Function Call countPairs(arr, N); } } // This code is contributed by code_hunt. |
Python3
MAX = 1005 ; def preCalculate(phi,ans): phi[ 0 ] = 0 phi[ 1 ] = 1 # Iterate over the range [1, MAX] for i in range ( 2 , MAX + 1 ): phi[i] = i # Iterate over the range [1, MAX] for i in range ( 2 , MAX + 1 ): if (phi[i] = = i): for j in range (i, MAX + 1 , i): # Subtract the number of # pairs which has i as one # of their factors phi[j] - = (phi[j] / / i); # Iterate over the range [1, MAX] for i in range ( 1 , MAX + 1 ): ans[i] = ans[i - 1 ] + (i - phi[i]); # Function to count the number of # non co-prime pairs for each query def countPairs(arr, N): # The i-th element stores # the count of element that # are co-prime with i phi = [ 0 for i in range ( 100001 )] # Stores the resulting array ans = [ 0 for i in range ( 100001 )] # Function Call preCalculate(phi, ans); # Traverse the array arr[] for i in range (N): print (ans[arr[i]],end = ' ' ); # Given Input arr = [ 5 , 10 , 20 ] N = 3 ; # Function Call countPairs(arr, N); # This code is contributed by rutvik_56. |
C#
// C# program for the above approach using System; class GFG{ static int MAX = 1005; // Auxiliary function to pre-compute // the answer for each array static void preCalculate( int [] phi, int [] ans) { phi[0] = 0; phi[1] = 1; // Iterate over the range [1, MAX] for ( int i = 2; i <= MAX; i++) phi[i] = i; // Iterate over the range [1, MAX] for ( int i = 2; i <= MAX; i++) { // If the number is prime if (phi[i] == i) { for ( int j = i; j <= MAX; j += i) // Subtract the number of // pairs which has i as one // of their factors phi[j] -= (phi[j] / i); } } // Iterate over the range [1, MAX] for ( int i = 1; i <= MAX; i++) ans[i] = ans[i - 1] + (i - phi[i]); } // Function to count the number of // non co-prime pairs for each query static void countPairs( int [] arr, int N) { // The i-th element stores // the count of element that // are co-prime with i int [] phi = new int [100000]; Array.Clear(phi, 0, 100000); // Stores the resulting array int [] ans = new int [100000]; Array.Clear(ans, 0, 100000); // Function Call preCalculate(phi, ans); // Traverse the array arr[] for ( int i = 0; i < N; ++i) { Console.Write(ans[arr[i]] + " " ); } } // Driver Code public static void Main() { // Given Input int [] arr = { 5, 10, 20 }; int N = 3; // Function Call countPairs(arr, N); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach const MAX = 1005; // Auxiliary function to pre-compute // the answer for each array function preCalculate(phi, ans) { phi[0] = 0; phi[1] = 1; // Iterate over the range [1, MAX] for (let i = 2; i <= MAX; i++) phi[i] = i; // Iterate over the range [1, MAX] for (let i = 2; i <= MAX; i++) { // If the number is prime if (phi[i] == i) { for (let j = i; j <= MAX; j += i) // Subtract the number of // pairs which has i as one // of their factors phi[j] -= Math.floor(phi[j] / i); } } // Iterate over the range [1, MAX] for (let i = 1; i <= MAX; i++) ans[i] = ans[i - 1] + (i - phi[i]); } // Function to count the number of // non co-prime pairs for each query function countPairs(arr, N) { // The i-th element stores // the count of element that // are co-prime with i let phi = new Array(1e5).fill(0); // Stores the resulting array let ans = new Array(1e5).fill(0); // Function Call preCalculate(phi, ans); // Traverse the array arr[] for (let i = 0; i < N; ++i) { document.write(ans[arr[i]] + " " ); } } // Driver Code // Given Input let arr = [5, 10, 20]; let N = 3; // Function Call countPairs(arr, N); </script> |
5 23 82
Time Complexity: O(N+ M*log(N)), where M is the maximum element of the array.
Auxiliary Space: O(M+N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!