Given an array arr[]of size N. We have to pair the integers such that each integer should be in exactly one pair and each sum of pairs is consecutive and distinct. Formally, sum(arri + arrj) + 1 = sum(arri1 + arrj1). Print the pairs of integers satisfying all the conditions. If it is not possible to find the pairs return -1.
Examples:
Input: N = 6, arr[] = {2, 3, 1, 4, 6, 5}
Output:
1 6
3 5
4 2
Explanation: All pair’s sum is consecutive.Input: N = 8 arr[] = {8, 7, 1, 2, 3, 5, 6, 4}
Output: -1
Approach: This can be solved with the following idea:
As we can choose any pair and as the array is a permutation we can ignore the arrangement in the array. Let’s assume that 1 to N is paired and each sum of the pair is: s, s + 1, ⋯, s + n/2 − 1. As the sum of the total number is equal to the sum s to s + n/2 − 1, we can obtain:
- N(N + 1)/2 = (s + N/2 − 1 + s)N/4
- or, 2N + 2 = 2S + N/2 – 1
- let P = N/2.
- or 4P + 2 = 2S + P + 1
- as LHS = always even so P must be odd if P is even, then the answer will be -1.
If N/2 is even then we can find the pairs. Here is a pattern:
Fig: Pattern in the numbers
Steps involved in the implementation of code:
- At first sort the array arr[].
- We have to start pairing from the middle two elements and go to the next right element and pair this element to the one before the element of the previous paired element.
- After doing till the first element We have to pair the second element with the last element and the fourth element with the second last element.
Below is the implementation of the above approach:
C++
// C++ implementation of the code
#include <bits/stdc++.h>
using namespace std;
// Function to find pairs
void findPairs(int n, int a[])
{
// N is reduced to N/2 for ease in
// calculation
n = n / 2;
int end, start;
// We can neglect the array
if (n % 2 == 0) {
// If the N/2 is even
cout << -1 << endl;
}
else {
int last = 2 * n;
start = last / 2;
end = start;
start++;
// To the next right element and
// pair this element to the one
// before the element of the
// previous paired element
while (end > 0) {
cout << start << " " << end << endl;
start++;
end -= 2;
}
// The first element We have to
// pair the second element with
// the last element and the
// fourth element with the second
// last element.
end = 2;
start = last;
while (end < (n + 1)) {
cout << start << " " << end << endl;
start--;
end += 2;
}
}
return;
}
// Driver code
int main()
{
int n = 6;
int a[] = { 2, 1, 5, 4, 6, 3 };
// Function call
findPairs(n, a);
return 0;
}
Java
// Java implementation of the code
import java.util.*;
class GFG {
// Function to find pairs
static void findPairs(int n, int[] a)
{
// N is reduced to N/2 for ease
// in calculation
n = n / 2;
int end, start;
// We can neglect the array
if (n % 2 == 0) {
// If the N/2 is even
System.out.println("-1");
}
else {
int last = 2 * n;
start = last / 2;
end = start;
start++;
// To the next right element and
// pair this element to the one
// before the element of the
// previous paired element
while (end > 0) {
System.out.println(start + " " + end);
start++;
end -= 2;
}
// The first element We have to
// pair the second element with
// the last element and the
// fourth element with the second
// last element.
end = 2;
start = last;
while (end < (n + 1)) {
System.out.println(start + " " + end);
start--;
end += 2;
}
}
return;
}
// Driver code
public static void main(String[] args)
{
int n = 6;
int[] a = { 2, 1, 5, 4, 6, 3 };
// Function call
findPairs(n, a);
}
}
// This code is contributed by Prasad Kandekar(prasad264)
Python3
# Function to find pairs
def find_pairs(n, a):
# N is reduced to N/2 for ease in calculation
n = n // 2
end, start = None, None
# We can neglect the array
if n % 2 == 0:
# If the N/2 is even
print(-1)
else:
last = 2 * n
start = last // 2
end = start
start += 1
# To the next right element and pair this element to the one
# before the element of the previous paired element
while end > 0:
print(start, end)
start += 1
end -= 2
# The first element We have to pair the second element with
# the last element and the fourth element with the second
# last element.
end = 2
start = last
while end < n + 1:
print(start, end)
start -= 1
end += 2
# Driver code
if __name__ == '__main__':
n = 6
a = [2, 1, 5, 4, 6, 3]
# Function call
find_pairs(n, a)
Javascript
// JavaScript implementation of the code
// Function to find pairs
function findPairs(n, a) {
// N is reduced to N/2 for ease in
// calculation
n = Math.floor(n / 2);
let end, start;
// We can neglect the array
if (n % 2 == 0) {
// If the N/2 is even
console.log(-1);
}
else {
let last = 2 * n;
start = Math.floor(last / 2);
end = start;
start++;
// To the next right element and
// pair this element to the one
// before the element of the
// previous paired element
while (end > 0) {
console.log(start + " " + end);
start++;
end -= 2;
}
// The first element We have to
// pair the second element with
// the last element and the
// fourth element with the second
// last element.
end = 2;
start = last;
while (end < (n + 1)) {
console.log(start + " " + end);
start--;
end += 2;
}
}
}
// Driver code
let n = 6;
let a = [2, 1, 5, 4, 6, 3];
// Function call
findPairs(n, a);
C#
using System;
public class Program
{
// Function to find pairs
public static void FindPairs(int n, int[] a)
{
// N is reduced to N/2 for ease in calculation
n = n / 2;
int end, start;
// We can neglect the array
if (n % 2 == 0)
{
// If the N/2 is even
Console.WriteLine("-1");
}
else
{
int last = 2 * n;
start = last / 2;
end = start;
start++;
// To the next right element and
// pair this element to the one
// before the element of the
// previous paired element
while (end > 0)
{
Console.WriteLine(start + " " + end);
start++;
end -= 2;
}
// The first element We have to
// pair the second element with
// the last element and the
// fourth element with the second
// last element.
end = 2;
start = last;
while (end < (n + 1))
{
Console.WriteLine(start + " " + end);
start--;
end += 2;
}
}
}
public static void Main()
{
int n = 6;
int[] a = new int[] { 2, 1, 5, 4, 6, 3 };
// Function call
FindPairs(n, a);
}
}
Output
4 3 5 1 6 2
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
