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 subsequencesvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Function to split the array// into two subsequencesstatic 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 Codepublic 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 subsequencesdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function to split the array// into two subsequencesstatic 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 Codepublic 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 subsequencesfunction 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 Codevar arr = [ 1, 5, 4, 3, 6, 2, 4, 3 ];var X = 7;// Size of the arrayvar N = arr.length;// Function Callsolve(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)
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!
