Split array into two subsequences having minimum count of pairs with sum equal to X

0 0 7 minutes read

Given an array arr[] consisting of N integers and an integer X, the task is to split the array into two subsequences such that the number of pairs having a sum equal to X is minimum in both the arrays.

Examples:

Input: arr[] = {1, 2, 3, 4, 5, 6}, X = 7
Output:
The First Array is – 1 2 3
The Second Array is – 4 5 6
Explanation:
The possible 3 pairs in the first array are {(1, 2), (2, 3), (1, 3)}. None of these pairs have sum equal to X (= 7).
The possible 3 pairs in the second array are {(4, 5), (5, 6), (4, 6)}. None of these pairs have sum equal to X (= 7).

Input: arr[] = {3, 3, 3}, X = 6
Output:
The First Array is – 3
The Second Array is – 3 3

Approach: Follow the steps below to solve the problem:

Create two arrays to store the two splitted subsequences.
Traverse the array and perform the following operations:
- If arr[i] * 2 < X: Insert it into the first array.
- Since the first array contains all numbers less than X / 2 currently, thus no pair has a sum equal to X in the array currently.
- If arr[i] * 2 > X: Insert it into the second array.
- Since the second array contains all numbers greater than X / 2 currently, thus no pair has a sum equal to X in the array currently.
- If arr[i] * 2 < X: Insert alternatively the elements into the first and second array respectively to get the minimum pairs.
Finally, after complete traversal of the array, print both the arrays.

Below is the implementation of the above approach:

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to split the array
// into two subsequences
void solve(int arr[], int N, int X)
{
    // Stores the two subsequences
    vector<int> A, B;
 
    // Flag to set/reset to split
    // arrays elements alternately
    // into two arrays
    int c = 0;
 
    // Traverse the given array
    for (int i = 0; i < N; i++) {
 
        // If 2 * arr[i] is less than X
        if ((2 * arr[i]) < X) {
 
            // Push element into
            // the first array
            A.push_back(arr[i]);
        }
 
        // If 2 * arr[i] is greater than X
        else if ((2 * arr[i]) > X) {
 
            // Push element into
            // the second array
            B.push_back(arr[i]);
        }
 
        // If 2 * arr[i] is equal to X
        else {
 
            // Alternatively place the
            // elements into the two arrays
            if (c % 2 == 0) {
 
                A.push_back(arr[i]);
            }
            else {
 
                B.push_back(arr[i]);
            }
            c++;
        }
    }
 
    // Print both the arrays
    cout << "The First Array is - ";
    for (int i = 0; i < A.size(); i++) {
 
        cout << A[i] << " ";
    }
    cout << endl;
    cout << "The Second Array is - ";
    for (int i = 0; i < B.size(); i++) {
 
        cout << B[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 4, 3,
                  6, 2, 4, 3 };
    int X = 7;
 
    // Size of the array
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    // Function Call
    solve(arr, N, X);
}

Java

// Java program for the 
// above approach
import java.util.*;
class GFG{
 
// Function to split the array
// into two subsequences
static void solve(int arr[], 
                  int N, int X)
{
  // Stores the two subsequences
  Vector<Integer> A = 
         new Vector<Integer>(), 
   B = new Vector<Integer>();
 
  // Flag to set/reset to split
  // arrays elements alternately
  // into two arrays
  int c = 0;
 
  // Traverse the given array
  for (int i = 0; i < N; i++) 
  {
    // If 2 * arr[i] is 
    // less than X
    if ((2 * arr[i]) < X) 
    {
      // Push element into
      // the first array
      A.add(arr[i]);
    }
 
    // If 2 * arr[i] is greater 
    // than X
    else if ((2 * arr[i]) > X) 
    {
      // Push element into
      // the second array
      B.add(arr[i]);
    }
 
    // If 2 * arr[i] is 
    // equal to X
    else
    {
      // Alternatively place the
      // elements into the two arrays
      if (c % 2 == 0) 
      {
        A.add(arr[i]);
      }
      else
      {
        B.add(arr[i]);
      }
      c++;
    }
  }
 
  // Print both the arrays
  System.out.print("The First Array is - ");
  for (int i = 0; i < A.size(); i++) 
  {
    System.out.print(A.get(i) + " ");
  }
   
  System.out.println();
   
  System.out.print("The Second Array is - ");  
  for (int i = 0; i < B.size(); i++) 
  {
    System.out.print(B.get(i) + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  int arr[] = {1, 5, 4, 3,
               6, 2, 4, 3};
  int X = 7;
 
  // Size of the array
  int N = arr.length;
 
  // Function Call
  solve(arr, N, X);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for above approach
 
# Function to split the array
# into two subsequences
def solve(arr, N, X):
     
    # Stores the two subsequences
    A = []
    B = []
     
    # Flag to set/reset to split
    # arrays elements alternately
    # into two arrays
    c = 0
 
    # Traverse the given array
    for i in range(N):
 
        # If 2 * arr[i] is less than X
        if ((2 * arr[i]) < X):
 
            # Push element into
            # the first array
            A.append(arr[i])
 
        # If 2 * arr[i] is greater than X
        elif ((2 * arr[i]) > X):
 
            # Push element into
            # the second array
            B.append(arr[i])
 
        # If 2 * arr[i] is equal to X
        else:
             
            # Alternatively place the
            # elements into the two arrays
            if (c % 2 == 0):
                A.append(arr[i])
            else:
                B.append(arr[i])
                 
            c += 1
 
    # Print both the arrays
    print("The First Array is - ", end = " ")
    for i in range(len(A)):
        print(A[i], end = " ")
 
    print()
     
    print("The Second Array is - ", end = " ")
    for i in range(len(B)):
        print(B[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 5, 4, 3, 6, 2, 4, 3 ]
    X = 7
 
    # Size of the array
    N = len(arr)
 
    # Function Call
    solve(arr, N, X)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the 
// above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to split the array
// into two subsequences
static void solve(int []arr, 
                  int N, int X)
{
  // Stores the two subsequences
  List<int> A = 
       new List<int>(), 
   B = new List<int>();
 
  // Flag to set/reset to 
  // split arrays elements 
  // alternately into two 
  // arrays
  int c = 0;
 
  // Traverse the given array
  for (int i = 0; i < N; i++) 
  {
    // If 2 * arr[i] is 
    // less than X
    if ((2 * arr[i]) < X) 
    {
      // Push element into
      // the first array
      A.Add(arr[i]);
    }
 
    // If 2 * arr[i] is greater 
    // than X
    else if ((2 * arr[i]) > X) 
    {
      // Push element into
      // the second array
      B.Add(arr[i]);
    }
 
    // If 2 * arr[i] is 
    // equal to X
    else
    {
      // Alternatively place the
      // elements into the two arrays
      if (c % 2 == 0) 
      {
        A.Add(arr[i]);
      }
      else
      {
        B.Add(arr[i]);
      }
      c++;
    }
  }
 
  // Print both the arrays
  Console.Write("The First Array is - ");
  for (int i = 0; i < A.Count; i++) 
  {
    Console.Write(A[i] + " ");
  }
   
  Console.WriteLine();
   
  Console.Write("The Second Array is - ");  
  for (int i = 0; i < B.Count; i++) 
  {
    Console.Write(B[i] + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {1, 5, 4, 3,
               6, 2, 4, 3};
  int X = 7;
 
  // Size of the array
  int N = arr.Length;
 
  // Function Call
  solve(arr, N, X);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for above approach
 
// Function to split the array
// into two subsequences
function solve(arr, N, X)
{
     
    // Stores the two subsequences
    var A = [], B = [];
 
    // Flag to set/reset to split
    // arrays elements alternately
    // into two arrays
    var c = 0;
 
    // Traverse the given array
    for(var i = 0; i < N; i++) 
    {
         
        // If 2 * arr[i] is less than X
        if ((2 * arr[i]) < X) 
        {
             
            // Push element into
            // the first array
            A.push(arr[i]);
        }
 
        // If 2 * arr[i] is greater than X
        else if ((2 * arr[i]) > X)
        {
             
            // Push element into
            // the second array
            B.push(arr[i]);
        }
 
        // If 2 * arr[i] is equal to X
        else
        {
 
            // Alternatively place the
            // elements into the two arrays
            if (c % 2 == 0) 
            {
                A.push(arr[i]);
            }
            else
            {
                B.push(arr[i]);
            }
            c++;
        }
    }
 
    // Print both the arrays
    document.write( "The First Array is - ");
    for(var i = 0; i < A.length; i++)
    {
        document.write( A[i] + " ");
    }
    document.write("<br>");
    document.write( "The Second Array is - ");
    for(var i = 0; i < B.length; i++) 
    {
        document.write( B[i] + " ");
    }
}
 
// Driver Code
var arr = [ 1, 5, 4, 3, 6, 2, 4, 3 ];
var X = 7;
 
// Size of the array
var N = arr.length;
 
// Function Call
solve(arr, N, X);
 
// This code is contributed by noob2000
 
</script>

Output

The First Array is - 1 3 2 3 
The Second Array is - 5 4 6 4

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!