Maximum count of pairs in Array with GCD greater than 1 by reordering given Array
Given an array arr[] of size N. The task is to reorder arr[] and find the maximum number of GCD pairs which follows the conditions given below.
- Choose any two elements of array Ai and Aj of array where 0 <= i < j < N.
- Calculate GCD after multiplying Aj with 2 like (Ai, 2 * Aj) which is greater than 1.
Examples
Input: arr[] = { 3, 6 . 5, 3}
Output: 4
Explanation: Reorder array like this : { 6, 5, 3, 3 } and below are the pairs formed from arr[].
P1 = GCD( 6, 5 * 2) => (6, 10) => 2 > 1
P2 = GCD( 6, 3 * 2) => (6, 6) => 6 > 1
P3 = GCD( 6, 3 * 2) => (6, 6) => 6 > 1
P4 = GCD( 3, 3 * 2) => (3, 6) => 3 > 1Input: arr[] = { 1, 7 }
Output: 0
Explanation: If array is order like { 7, 1 } no pair can be formed
GCD(7, 1 * 2) = > (7, 2 ), GCD(1, 7 * 2) => (1, 14) == 1
Approach: If we observe that if even elements are in starting position then the pairs of (GCD > 1) is maximum because there is a condition to multiply the arr[j] * 2, and the ordering of odd elements does not matter its number of pair always same. Follow the steps below to solve the given problem.
- Initialize the variable idx with value 0.
- Traverse the array.
- If arr[i] is even then swap with arr[idx] and increment idx by 1.
- After traversing all the elements.
- Initialize the variable ans with 0.
- Use two loops first with i and second with j = i + 1.
- Now if gcd(arr[i], 2 * arr[j] * 2) > 1 increment the ans by 1.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum number of pairs int maximumpairs( int arr[], int n) { // Reorder array with even element first int idx = 0; for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 0) { swap(arr[i], arr[idx]); idx++; } } // Now count the ans int ans = 0; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { if (__gcd(arr[i], 2 * arr[j]) > 1) { ans++; } } } return ans; } // Driver Code int main() { // Initializations int arr[] = { 5, 3, 6, 3 }; int N = sizeof (arr) / sizeof ( int ); // Function Call int ans = maximumpairs(arr, N); cout << ans; return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // find gcd static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to find the maximum number of pairs static int maximumpairs( int arr[], int n) { // Reorder array with even element first int idx = 0 ; for ( int i = 0 ; i < n; i++) { if (arr[i] % 2 == 0 ) { //swap int temp = arr[i]; arr[i] = arr[idx]; arr[idx] = temp; idx++; } } // Now count the ans int ans = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { int a = arr[i]; int b = 2 * arr[j]; if (gcd(a, b) > 1 ) { ans++; } } } return ans; } public static void main (String[] args) { // Initializations int arr[] = { 5 , 3 , 6 , 3 }; int N = arr.length; // Function Call int ans = maximumpairs(arr, N); System.out.println(ans); } } // This code is contributed by hrithikgarg03188 |
Python3
# Python program for above approach # Function to find GCD def gcd(a, b): if (b = = 0 ): return a else : return gcd(b, a % b) # Function to find the maximum number of pairs def maximumpairs(arr,n): # Reorder array with even element first idx = 0 for i in range ( 0 , n): if (arr[i] % 2 = = 0 ): arr[i], arr[idx] = arr[idx], arr[i] idx = idx + 1 # Now count the ans ans = 0 for i in range ( 0 ,n): for j in range (i + 1 ,n): if (gcd(arr[i], 2 * arr[j]) > 1 ): ans = ans + 1 return ans # Driver Code # Initializations arr = [ 5 , 3 , 6 , 3 ] N = len (arr) # Function Call ans = maximumpairs(arr, N) print (ans) # This code is contributed by Taranpreet |
C#
// C# program for the above approach using System; class GFG { // find gcd static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the maximum number of pairs static int maximumpairs( int []arr, int n) { // Reorder array with even element first int idx = 0; for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 0) { //swap int temp = arr[i]; arr[i] = arr[idx]; arr[idx] = temp; idx++; } } // Now count the ans int ans = 0; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { int a = arr[i]; int b = 2 * arr[j]; if (gcd(a, b) > 1) { ans++; } } } return ans; } public static void Main () { // Initializations int []arr = { 5, 3, 6, 3 }; int N = arr.Length; // Function Call int ans = maximumpairs(arr, N); Console.Write(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // find gcd function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the maximum number of pairs function maximumpairs(arr, n) { // Reorder array with even element first let idx = 0; for (let i = 0; i < n; i++) { if (arr[i] % 2 == 0) { //swap let temp = arr[i]; arr[i] = arr[idx]; arr[idx] = temp; idx++; } } // Now count the ans let ans = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { let a = arr[i]; let b = 2 * arr[j]; if (gcd(a, b) > 1) { ans++; } } } return ans; } // Initializations let arr = [ 5, 3, 6, 3 ]; let N = arr.length; // Function Call let ans = maximumpairs(arr, N); document.write(ans); // This code is contributed by Samim Hossain Mondal. </script> |
4
Time Complexity: O(N * N * logN)
Auxiliary Space: O(1)