Select Page

# Find if new Array can be formed from given two Arrays.

Team 1 - Programming
Published: December 27, 2022
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;

// Dp table initialized with - 1
int dp[200001][3];

// Recusive function to tell whether new
// array can be formed from given
// two arrays
int recur(int i, int j, int k, int arr1[], int arr2[],
int N)
{

// Base case
if (i == N) {

// Return 1 as the creation of
// new array of size N is possible
return 1;
}

// If current state is precomputed then
// just return already computed value
if (dp[i][j + 1] != -1)
return dp[i][j + 1];

// Answer initialized with considering
// no possibility
int ans = 0;

// First element to be choosen
if (j == -1) {

// Taking first element from arr1[]
ans = recur(i + 1, 0, k, arr1, arr2, N);

// Taking first element from arr2[]
ans = max(ans, recur(i + 1, 1, k, arr1, arr2, N));
}

// Last elemet was choosen from
// first array
else if (j == 0) {

// If the absolute difference with
// previous element choosen is less
// than equal to K then choose arr2[i]
if (abs(arr2[i] - arr1[i - 1]) <= k)
ans = recur(i + 1, 1, k, arr1, arr2, N);

// If the absolute difference with
// previous element choosen is less than
// equal to K then choose arr1[i]
if (abs(arr1[i] - arr1[i - 1]) <= k)
ans = max(ans,
recur(i + 1, 0, k, arr1, arr2, N));
}

// Last element was choosen from
// second array
else {

// If the absolute difference with
// previous element choosen is less than
// equal to K then choose arr2[i]
if (abs(arr2[i] - arr2[i - 1]) <= k)
ans = recur(i + 1, 1, k, arr1, arr2, N);

// If the absolute difference with
// previous element choosen is less
// than equal to K then choose arr1[i]
if (abs(arr1[i] - arr2[i - 1]) <= k)
ans = max(ans,
recur(i + 1, 0, k, arr1, arr2, N));
}

// Save and return dp value
return dp[i][j + 1] = ans;
}

// Function to find whether new array
// can be formed from the given two
// arrays
void isNewArrayPossible(int arr1[], int arr2[], int N,
int K)
{

// Filling dp table with -1
memset(dp, -1, sizeof(dp));

// If recur funtion returns one then
// it is possible else it is not
if (recur(0, -1, K, arr1, arr2, N))
cout << "Yes" << endl;
else
cout << "No" << endl;
}

// Driver Code
int main()
{

// Input
int arr1[] = { 9, 8, 3, 7, 2 },
arr2[] = { 1, 6, 2, 9, 5 };
int N = sizeof(arr1) / sizeof(arr1[0]);
int K = 4;

// Function Call
isNewArrayPossible(arr1, arr2, N, K);

// Input2
int arr3[] = { 1, 1, 1, 100 },
arr4[] = { 1, 2, 3, 100 };
int N1 = sizeof(arr3) / sizeof(arr3[0]);
int K1 = 90;

// Function call
isNewArrayPossible(arr3, arr4, N1, K1);
return 0;
}

Source: www.geeksforgeeks.org