Given an array arr[] of even size, the task is to find the count of pairs after partitioning arr[] into pairs, such that:
- each element of arr[] belongs to exactly one pair
- both of them are even or
- absolute difference between them is 1, i.e, |X – Y| = 1.
Examples:
Input: arr[] = {11, 12, 16, 14}
Output: {11, 12}, {16, 14}
Explanation: arr[] can be partitioned into pairs in the following way.
Pair 1 – {11, 12}, as |11-12| = 1.
Pair 2 – {16, 14}, both 16 and 14 are even.
Therefore, {11, 12} and {16, 14} are the two pairs.Input: A = {4, 7}
Output: No
Approach: This problem is observation-based. Firstly, if even numbers count and odd numbers count does not have the same parity then the answer does not exist. That means if the count of even and odd both are either even or both are either odd. Now the left case when even numbers and odd numbers are equal in frequency, then 2 cases are there:
- Occurrence of even and odd numbers are even, then answer exists always.
- Occurrence even and odd numbers are odd, then check if there are 2 numbers in the array such that their absolute difference is 1, and then even and odd numbers occurrence becomes, even so, answer exist.
Follow the steps below to solve the given problem.
- Create a variable even_count = 0 as count of even numbers and odd_count = 0, as count of odd numbers.
- Iterate the array from index = 0 to n-1, check if arr[index]%2 == 0, increment even_count else increment odd_count.
- Check if even_count = odd_count
- if condition false output No as the array pairs cannot exist.
- Else check if there exist 2 elements in the array such that their absolute difference is 1. To check such a pair exists, create an array temp and store the count of each number of the array, then iterate the array and check if the consecutive element count is greater than 1 or not.
- If exists output Yes.
- For printing the required pairs, print even numbers in pairs, then odd numbers in pairs, and the left 2 elements as the last pair.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find similar pairs in arr[]void CheckSimilarPair(int arr[], int n){ // Variable to count // Odd and even numbers int odd_count = 0; int even_count = 0; // Count even and odd occurrences for (int index = 0; index < n; index++) { if (arr[index] % 2 == 0) even_count++; else odd_count++; } // Checking same parity of count of even // and odd numbers if ((even_count % 2 == 0 && odd_count % 2 == 1) || (even_count % 2 == 1 && odd_count % 2 == 0)) { cout << "-1\n"; } else { // Check if there exist 2 numbers // with absolute difference is 1 // Vector to store frequency // of elements of the array vector<int> temp(1001, 0); // Maximum element upto which // temp should be checked int max_element = 0; // Iterate the array and store their counts for (int index = 0; index < n; index++) { temp[arr[index]]++; max_element = max(max_element, arr[index]); } int element1 = -1; int element2 = -1; bool pair_exist = false; // Iterate the temp array // upto max_element and check // if 2 element exist // having 1 abs' difference for (int index = 1; index <= max_element; index++) { if (temp[index - 1] >= 1 && temp[index] >= 1) { element1 = index - 1; element2 = index; pair_exist = true; break; } } // If pair exist if (pair_exist) { // Vector storing pairs vector<int> res; // Even pairs for (int index = 0; index < n; index++) { if (arr[index] % 2 == 0 && arr[index] != element1 && arr[index] != element2) { res.push_back(arr[index]); } } // Odd pairs for (int index = 0; index < n; index++) { if (arr[index] % 2 == 1 && arr[index] != element1 && arr[index] != element2) { res.push_back(arr[index]); } } // Printing all pairs for (int index = 0; index < res.size() - 1; index += 2) { cout << "{" << res[index] << ", " << res[index + 1] << "}" << " "; } cout << "{" << element1 << ", " << element2 << "}"; } else { cout << "\nNo"; } }}// Driver codeint main(){ int arr[4] = { 11, 12, 16, 14 }; int N = 4; CheckSimilarPair(arr, N); return 0;} |
Java
// Java program for above approachimport java.util.*;class GFG{// Function to find similar pairs in arr[]static void CheckSimilarPair(int arr[], int n){ // Variable to count // Odd and even numbers int odd_count = 0; int even_count = 0; // Count even and odd occurrences for (int index = 0; index < n; index++) { if (arr[index] % 2 == 0) even_count++; else odd_count++; } // Checking same parity of count of even // and odd numbers if ((even_count % 2 == 0 && odd_count % 2 == 1) || (even_count % 2 == 1 && odd_count % 2 == 0)) { System.out.print("-1\n"); } else { // Check if there exist 2 numbers // with absolute difference is 1 // Vector to store frequency // of elements of the array int []temp = new int[1001]; // Maximum element upto which // temp should be checked int max_element = 0; // Iterate the array and store their counts for (int index = 0; index < n; index++) { temp[arr[index]]++; max_element = Math.max(max_element, arr[index]); } int element1 = -1; int element2 = -1; boolean pair_exist = false; // Iterate the temp array // upto max_element and check // if 2 element exist // having 1 abs' difference for (int index = 1; index <= max_element; index++) { if (temp[index - 1] >= 1 && temp[index] >= 1) { element1 = index - 1; element2 = index; pair_exist = true; break; } } // If pair exist if (pair_exist) { // Vector storing pairs Vector<Integer> res = new Vector<Integer>(); // Even pairs for (int index = 0; index < n; index++) { if (arr[index] % 2 == 0 && arr[index] != element1 && arr[index] != element2) { res.add(arr[index]); } } // Odd pairs for (int index = 0; index < n; index++) { if (arr[index] % 2 == 1 && arr[index] != element1 && arr[index] != element2) { res.add(arr[index]); } } // Printing all pairs for (int index = 0; index < res.size() - 1; index += 2) { System.out.print("{" + res.get(index)+ ", " + res.get(index+1)+ "}" + " "); } System.out.print("{" + element1+ ", " + element2+ "}"); } else { System.out.print("\nNo"); } }}// Driver codepublic static void main(String[] args){ int arr[] = { 11, 12, 16, 14 }; int N = 4; CheckSimilarPair(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python program for above approach# Function to find similar pairs in arr[]def CheckSimilarPair(arr, n): # Variable to count # Odd and even numbers odd_count = 0 even_count = 0 # Count even and odd occurrences for index in range(n): if (arr[index] % 2 == 0): even_count += 1 else: odd_count += 1 # Checking same parity of count of even # and odd numbers if ((even_count % 2 == 0 and odd_count % 2 == 1) or (even_count % 2 == 1 and odd_count % 2 == 0)): print("-1") else: # Check if there exist 2 numbers # with absolute difference is 1 # Vector to store frequency # of elements of the array temp = [0] * 1001 # Maximum element upto which # temp should be checked max_element = 0 # Iterate the array and store their counts for index in range(n): temp[arr[index]] += 1 max_element = max(max_element, arr[index]) element1 = -1 element2 = -1 pair_exist = False # Iterate the temp array # upto max_element and check # if 2 element exist # having 1 abs' difference for index in range(max_element + 1): if (temp[index - 1] >= 1 and temp[index] >= 1): element1 = index - 1 element2 = index pair_exist = True break # If pair exist if (pair_exist): # Vector storing pairs res = [] # Even pairs for index in range(n): if (arr[index] % 2 == 0 and arr[index] != element1 and arr[index] != element2): res.append(arr[index]) # Odd pairs for index in range(n): if (arr[index] % 2 == 1 and arr[index] != element1 and arr[index] != element2): res.append(arr[index]) # Printing all pairs for index in range(0, len(res) - 1, 2): print("{", end=" ") print(f"{res[index]} , {res[index + 1]}", end=" ") print("}", end=" ") print("{", end=" ") print(f"{element1} ,{element2}", end=" ") print("}") else: print('<br>' + "No")# Driver codearr = [11, 12, 16, 14]N = 4CheckSimilarPair(arr, N)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections;class GFG{// Function to find similar pairs in arr[]static void CheckSimilarPair(int []arr, int n){ // Variable to count // Odd and even numbers int odd_count = 0; int even_count = 0; // Count even and odd occurrences for (int index = 0; index < n; index++) { if (arr[index] % 2 == 0) even_count++; else odd_count++; } // Checking same parity of count of even // and odd numbers if ((even_count % 2 == 0 && odd_count % 2 == 1) || (even_count % 2 == 1 && odd_count % 2 == 0)) { Console.Write("-1\n"); } else { // Check if there exist 2 numbers // with absolute difference is 1 // Vector to store frequency // of elements of the array int []temp = new int[1001]; // Maximum element upto which // temp should be checked int max_element = 0; // Iterate the array and store their counts for (int index = 0; index < n; index++) { temp[arr[index]]++; max_element = Math.Max(max_element, arr[index]); } int element1 = -1; int element2 = -1; bool pair_exist = false; // Iterate the temp array // upto max_element and check // if 2 element exist // having 1 abs' difference for (int index = 1; index <= max_element; index++) { if (temp[index - 1] >= 1 && temp[index] >= 1) { element1 = index - 1; element2 = index; pair_exist = true; break; } } // If pair exist if (pair_exist) { // Vector storing pairs ArrayList res = new ArrayList(); // Even pairs for (int index = 0; index < n; index++) { if (arr[index] % 2 == 0 && arr[index] != element1 && arr[index] != element2) { res.Add(arr[index]); } } // Odd pairs for (int index = 0; index < n; index++) { if (arr[index] % 2 == 1 && arr[index] != element1 && arr[index] != element2) { res.Add(arr[index]); } } // Printing all pairs for (int index = 0; index < res.Count - 1; index += 2) { Console.Write("{" + res[index]+ ", " + res[index+1]+ "}" + " "); } Console.Write("{" + element1+ ", " + element2+ "}"); } else { Console.Write("\nNo"); } }}// Driver Codepublic static void Main(){ int []arr = { 11, 12, 16, 14 }; int N = 4; CheckSimilarPair(arr, N);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program for above approach // Function to find similar pairs in arr[]function CheckSimilarPair(arr, n) { // Variable to count // Odd and even numbers let odd_count = 0; let even_count = 0; // Count even and odd occurrences for(let index = 0; index < n; index++) { if (arr[index] % 2 == 0) even_count++; else odd_count++; } // Checking same parity of count of even // and odd numbers if ((even_count % 2 == 0 && odd_count % 2 == 1) || (even_count % 2 == 1 && odd_count % 2 == 0)) { cout << "-1\n"; } else { // Check if there exist 2 numbers // with absolute difference is 1 // Vector to store frequency // of elements of the array let temp = new Array(1001).fill(0) // Maximum element upto which // temp should be checked let max_element = 0; // Iterate the array and store their counts for(let index = 0; index < n; index++) { temp[arr[index]]++; max_element = Math.max(max_element, arr[index]); } let element1 = -1; let element2 = -1; let pair_exist = false; // Iterate the temp array // upto max_element and check // if 2 element exist // having 1 abs' difference for(let index = 1; index <= max_element; index++) { if (temp[index - 1] >= 1 && temp[index] >= 1) { element1 = index - 1; element2 = index; pair_exist = true; break; } } // If pair exist if (pair_exist) { // Vector storing pairs let res = []; // Even pairs for(let index = 0; index < n; index++) { if (arr[index] % 2 == 0 && arr[index] != element1 && arr[index] != element2) { res.push(arr[index]); } } // Odd pairs for(let index = 0; index < n; index++) { if (arr[index] % 2 == 1 && arr[index] != element1 && arr[index] != element2) { res.push(arr[index]); } } // Printing all pairs for(let index = 0; index < res.length - 1; index += 2) { document.write("{" + res[index] + ", " + res[index + 1] + "}" + " "); } document.write("{" + element1 + ", " + element2 + "}"); } else { document.write('<br>' + "No"); } }}// Driver codelet arr = [ 11, 12, 16, 14 ];let N = 4;CheckSimilarPair(arr, N);// This code is contributed by Potta Lokesh</script> |
Output
{16, 14} {11, 12}
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
