Find N – 1 pairs from given array such that GCD of all pair-sums is greater than 1
Given an array arr[] of 2 * N integers, the task is to find a set of N – 1 pairs such that the GCD of all pair sums is greater than 1.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}
Output:
1 3
2 4
Explanation: The given array has 3 * 2 elements. The pair (1, 3) and (2, 4) has sum of elements as 4 and 6 respectively. Also, GCD(4, 6) > 1. Hence, (1, 3) and (2, 4) are the required pairs. Other possible pairs are (1, 5) and (2, 6), (3, 5) and (2, 5), etc..Input: arr[] = {1, 1, 1, 2, 3, 4}
Output:
1 3
2 4
Approach: The given problem is an observation-based problem. The idea is the create N – 1 pairs such that their sum is even. Also, for a pair to have an even sum, either both the integers should be even or both should be odd. Below are the steps to follow:
Below is the implementation of the above approach:
C++
// C++ Program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find N - 1 pairs from // given array such that GCD of all // pair-sums is greater than 1 void findPairs( int arr[], int N) { // Stores even and odd // integers respectively vector< int > even, odd; // Loop to iterate arr[] for ( int i = 0; i < 2 * N; i++) { if (arr[i] & 1) odd.push_back(arr[i]); else even.push_back(arr[i]); } // Stores the required pairs vector<pair< int , int > > ans; // Insert all possible pairs // from odd elements for ( int i = 0; i + 1 < odd.size(); i += 2) ans.push_back({ odd[i], odd[i + 1] }); // Insert all possible pairs // from even elements for ( int i = 0; i + 1 < even.size(); i += 2) ans.push_back({ even[i], even[i + 1] }); // Print Answer for ( int i = 0; i < N - 1; i++) { cout << ans[i].first << " " << ans[i].second << endl; } } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = 3; findPairs(arr, N); return 0; } |
Java
// JAVA Program of the above approach import java.util.*; class Pair { int x; int y; // Constructor public Pair( int x, int y) { this .x = x; this .y = y; } } class GFG { // Function to find N - 1 pairs from // given array such that GCD of all // pair-sums is greater than 1 public static void findPairs( int arr[], int N) { // Stores even and odd // integers respectively ArrayList<Integer> even = new ArrayList<Integer>(); ArrayList<Integer> odd = new ArrayList<Integer>(); // Loop to iterate arr[] for ( int i = 0 ; i < 2 * N; i++) { if (arr[i] % 2 == 1 ) odd.add(arr[i]); else even.add(arr[i]); } // Stores the required pairs Pair[] ans1 = new Pair[N]; Pair[] ans2 = new Pair[N]; // Insert all possible pairs // from odd elements for ( int i = 0 ; i + 1 < odd.size(); i += 2 ) { ans1[i] = new Pair(odd.get(i), odd.get(i + 1 )); } // Insert all possible pairs // from even elements for ( int i = 0 ; i + 1 < even.size(); i += 2 ) { ans2[i] = new Pair(even.get(i), even.get(i + 1 )); } // Print Answer for ( int i = 0 ; i < N - 1 ; i++) { System.out.println(ans1[i].x + " " + ans1[i].y); System.out.println(ans2[i].x + " " + ans2[i].y); break ; } } // Driver Code public static void main(String[] args) { int [] arr = new int [] { 1 , 2 , 3 , 4 , 5 , 6 }; int N = 3 ; findPairs(arr, N); } } // This code is contributed by Taranpreet |
Python3
# Python code for the above approach # Function to find N - 1 pairs from # given array such that GCD of all # pair-sums is greater than 1 def findPairs(arr, N): # Stores even and odd # integers respectively even = [] odd = []; # Loop to iterate arr[] for i in range ( 2 * N): if (arr[i] & 1 ): odd.append(arr[i]); else : even.append(arr[i]); # Stores the required pairs ans = []; # Insert all possible pairs # from odd elements i = 0 ; while (i + 1 < len (odd)): ans.append({ "first" : odd[i], "second" : odd[i + 1 ] }); i + = 2 # Insert all possible pairs # from even elements i = 0 while (i + 1 < len (odd)): ans.append({ "first" : even[i], "second" : even[i + 1 ] }); i + = 2 # Print Answer for i in range (N - 1 ): for y in ans[i].values(): print (y, end = " " ) print ("") # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 , 6 ]; N = 3 ; findPairs(arr, N); # This code is contributed by Saurabh Jaiswal |
C#
// C# Program of the above approach using System; using System.Collections.Generic; public class Pair { public int x; public int y; // Constructor public Pair( int x, int y) { this .x = x; this .y = y; } } public class GFG { // Function to find N - 1 pairs from // given array such that GCD of all // pair-sums is greater than 1 public static void findPairs( int []arr, int N) { // Stores even and odd // integers respectively List< int > even = new List< int >(); List< int > odd = new List< int >(); // Loop to iterate []arr for ( int i = 0; i < 2 * N; i++) { if (arr[i] % 2 == 1) odd.Add(arr[i]); else even.Add(arr[i]); } // Stores the required pairs Pair[] ans1 = new Pair[N]; Pair[] ans2 = new Pair[N]; // Insert all possible pairs // from odd elements for ( int i = 0; i + 1 < odd.Count; i += 2) { ans1[i] = new Pair(odd[i], odd[i + 1]); } // Insert all possible pairs // from even elements for ( int i = 0; i + 1 < even.Count; i += 2) { ans2[i] = new Pair(even[i], even[i + 1]); } // Print Answer for ( int i = 0; i < N - 1; i++) { Console.WriteLine(ans1[i].x + " " + ans1[i].y); Console.WriteLine(ans2[i].x + " " + ans2[i].y); break ; } } // Driver Code public static void Main(String[] args) { int [] arr = new int [] { 1, 2, 3, 4, 5, 6 }; int N = 3; findPairs(arr, N); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach // Function to find N - 1 pairs from // given array such that GCD of all // pair-sums is greater than 1 function findPairs(arr, N) { // Stores even and odd // integers respectively let even = [], odd = []; // Loop to iterate arr[] for (let i = 0; i < 2 * N; i++) { if (arr[i] & 1) odd.push(arr[i]); else even.push(arr[i]); } // Stores the required pairs let ans = []; // Insert all possible pairs // from odd elements for (let i = 0; i + 1 < odd.length; i += 2) ans.push({ first: odd[i], second: odd[i + 1] }); // Insert all possible pairs // from even elements for (let i = 0; i + 1 < even.length; i += 2) ans.push({ first: even[i], second: even[i + 1] }); // Print Answer for (let i = 0; i < N - 1; i++) { document.write(ans[i].first + " " + ans[i].second + "<br>" ); } } // Driver Code let arr = [1, 2, 3, 4, 5, 6]; let N = 3; findPairs(arr, N); // This code is contributed by Potta Lokesh </script> |
1 3 2 4
Time Complexity: O(N)
Auxiliary Space: O(N)