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