Given arrays A[] and B[] of size N, the task is to count ways to form an array of size N such that the new array formed has ith element either A[i] or B[i] and adjacent elements are different.
Examples:
Input: A[] = {1, 4, 3}, B[] = {2, 2, 4}
Output: 4
Explanation: Possible arrays are {1, 4, 3}, {1, 2, 3}, {1, 2, 4} and {2, 4, 3}.
Below is the Recursion Tree. Green is a valid move whereas red is an invalid move.
Â
Example-1
Input: A[] = {1, 2, 3, 4}, B[] = {5, 6, 7, 8}
Output: Â 16
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach/Memoization:Â The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem:
- dp[i][j] represents number of possible arrays of size i with last element chosen from array j (0 for A[] and 1 for B[]).
It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly.Â
So the idea is to store the value of each state. This can be done by storing the value of a state and whenever the function is called, returning the stored value without computing again.
Follow the steps below to solve the problem:
- Declare a dp array, dp[100001][2] initialized with -1 using memset() function.
- Create a 2d array Arr[][], whose first column will contain array A[] and the second column will have array B[].
- Create a recursive function that takes four parameters i and j such that i represents position and j represents the last element chosen from either A[] or B[], Arr[] stores array A[] and B[], and size of array N.
- Calling recursive function recur(0, 0, Arr, N) with i = 0 indicates we will fill the first position of the required array.
- Check if i == N, return 1.
- Check if dp[i][j] != -1, return dp[i][j].
- Initialize variable ans = 0 to count the number of valid solutions.
- Call recursive function for both choosing an element from A[] (in this case Arr[][0]) or B[] (in this case Arr[][1]) and add the answer returned to cnt .
- Return ans calculated for the current state.
- Save the answer in dp[i][j] before returning.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;Â
// mod to avoid integer overflowconst int mod = 1e9 + 7;Â
// dp tableint dp[100001][2];Â
// recursive Function to count ways to// form array of size N such that adjcent// elements chosen are differentint recur(int i, int j, vector<vector<int> >& Arr, int N){Â
    // If already computed state just    // return dp[i][j]    if (dp[i][j] != -1)        return dp[i][j];Â
    // If array of size N is possible    if (i == N)        return 1;Â
    // Answer initialized with value zero    int ans = 0;Â
    // if choosing element from A[]    if (i == 0 or Arr[i - 1][j] != Arr[i][0])        ans = (ans + recur(i + 1, 0, Arr, N)) % mod;Â
    // if choosing element from B[]    if (i == 0 or Arr[i - 1][j] != Arr[i][1])        ans = (ans + recur(i + 1, 1, Arr, N)) % mod;Â
    // Return the final answer    return dp[i][j] = ans;}Â
// Function to count ways to form// array of size N such that adjcent// elements chosen are differentvoid findWays(int A[], int B[], int N){Â
    // initializing dp table with - 1    memset(dp, -1, sizeof(dp));Â
    // making one array for A[] & B[]    vector<vector<int> > Arr(N, vector<int>(2));Â
    // filling Arr    for (int i = 0; i < N; i++) {        Arr[i][0] = A[i];        Arr[i][1] = B[i];    }Â
    // calling recursive function    cout << recur(0, 0, Arr, N) << endl;}Â
// Driver Codeint main(){Â
    // Input 1    int A[] = { 1, 4, 3 }, B[] = { 2, 2, 4 };    int N = sizeof(A) / sizeof(A[0]);Â
    // Function Call    findWays(A, B, N);Â
    // Input 2    int A1[] = { 1, 2, 3, 4 }, B1[] = { 5, 6, 7, 8 };    int N1 = sizeof(A1) / sizeof(A1[0]);Â
    // Function Call    findWays(A1, B1, N1);Â
    return 0;} |
Java
// Java code to implement the approachÂ
import java.io.*;import java.util.*;Â
class GFG {Â
    // mod to avoid integer overflow    static final int mod = (int)1e9 + 7;Â
    // dp table    static int[][] dp = new int[100001][2];Â
    // recursive Function to count ways to form array of    // size N such that adjacent elements chosen are    // different    static int recur(int i, int j, int[][] Arr, int N)    {Â
        // If already computed state just return dp[i][j]        if (dp[i][j] != -1)            return dp[i][j];Â
        // If array of size N is possible        if (i == N)            return 1;Â
        // Answer initialized with value zero        int ans = 0;Â
        // if choosing element from A[]        if (i == 0 || Arr[i - 1][j] != Arr[i][0])            ans = (ans + recur(i + 1, 0, Arr, N)) % mod;Â
        // if choosing element from B[]        if (i == 0 || Arr[i - 1][j] != Arr[i][1])            ans = (ans + recur(i + 1, 1, Arr, N)) % mod;Â
        // Return the final answer        return dp[i][j] = ans;    }Â
    // Function to count ways to form array of size N such    // that adjacent elements chosen are different    static void findWays(int[] A, int[] B, int N)    {Â
        // initializing dp table with -1        for (int i = 0; i <= N; i++) {            Arrays.fill(dp[i], -1);        }Â
        // making one array for A[] & B[]        int[][] Arr = new int[N][2];Â
        // filling Arr        for (int i = 0; i < N; i++) {            Arr[i][0] = A[i];            Arr[i][1] = B[i];        }Â
        // calling recursive function        System.out.println(recur(0, 0, Arr, N));    }Â
    public static void main(String[] args)    {        // Input 1        int[] A = { 1, 4, 3 };        int[] B = { 2, 2, 4 };        int N = A.length;Â
        // Function Call        findWays(A, B, N);Â
        // Input 2        int[] A1 = { 1, 2, 3, 4 };        int[] B1 = { 5, 6, 7, 8 };        int N1 = A1.length;Â
        // Function Call        findWays(A1, B1, N1);    }}Â
// This code is contributed by lokesh. |
Python
# python code to implement the approachMOD = int(1e9) + 7Â
# dp tabledp = [[-1 for j in range(2)] for i in range(100001)]Â
# recursive Function to count ways to# form array of size N such that adjacent# elements chosen are differentÂ
Â
def recur(i, j, arr, N):Â Â Â Â global dpÂ
    # If already computed state just    # return dp[i][j]    if dp[i][j] != -1:        return dp[i][j]Â
    # If array of size N is possible    if i == N:        return 1Â
    # Answer initialized with value zero    ans = 0Â
    # if choosing element from A[]    if i == 0 or arr[i - 1][j] != arr[i][0]:        ans = (ans + recur(i + 1, 0, arr, N)) % MODÂ
    # if choosing element from B[]    if i == 0 or arr[i - 1][j] != arr[i][1]:        ans = (ans + recur(i + 1, 1, arr, N)) % MODÂ
    # Return the final answer    dp[i][j] = ans    return ansÂ
# Function to count ways to form# array of size N such that adjacent# elements chosen are differentÂ
Â
def findWays(A, B, N):Â Â Â Â global dpÂ
    # making one array for A[] & B[]    arr = [[0 for j in range(2)] for i in range(N)]Â
    # filling arr    for i in range(N):        arr[i][0] = A[i]        arr[i][1] = B[i]Â
    # initializing dp table with -1    for i in range(100001):        dp[i][0] = dp[i][1] = -1Â
    # calling recursive function    print(recur(0, 0, arr, N))Â
Â
# Driver Codeif __name__ == '__main__':Â
    # Input 1    A = [1, 4, 3]    B = [2, 2, 4]    N = len(A)Â
    # Function Call    findWays(A, B, N)Â
    # Input 2    A1 = [1, 2, 3, 4]    B1 = [5, 6, 7, 8]    N1 = len(A1)Â
    # Function Call    findWays(A1, B1, N1)# This code is contributed by lokesh. |
C#
// C# code for the approachÂ
using System;Â
public class GFG {    // mod to avoid integer overflow    const int mod = 1000000007;Â
    // dp table    static int[, ] dp = new int[100001, 2];Â
    // recursive Function to count ways to    // form array of size N such that adjcent    // elements chosen are different    static int recur(int i, int j, int[][] Arr, int N)    {Â
        // If already computed state just        // return dp[i][j]        if (dp[i, j] != -1)            return dp[i, j];Â
        // If array of size N is possible        if (i == N)            return 1;Â
        // Answer initialized with value zero        int ans = 0;Â
        // if choosing element from A[]        if (i == 0 || Arr[i - 1][j] != Arr[i][0])            ans = (ans + recur(i + 1, 0, Arr, N)) % mod;Â
        // if choosing element from B[]        if (i == 0 || Arr[i - 1][j] != Arr[i][1])            ans = (ans + recur(i + 1, 1, Arr, N)) % mod;Â
        // Return the final answer        return dp[i, j] = ans;    }Â
    // Function to count ways to form    // array of size N such that adjcent    // elements chosen are different    static void findWays(int[] A, int[] B, int N)    {Â
        // initializing dp table with - 1        for (int i = 0; i < 100001; i++)            for (int j = 0; j < 2; j++)                dp[i, j] = -1;Â
        // making one array for A[] & B[]        int[][] Arr = new int[N][];Â
        // filling Arr        for (int i = 0; i < N; i++) {            Arr[i] = new int[2];            Arr[i][0] = A[i];            Arr[i][1] = B[i];        }Â
        // calling recursive function        Console.WriteLine(recur(0, 0, Arr, N));    }Â
    // Driver Code    public static void Main()    {Â
        // Input 1        int[] A = { 1, 4, 3 }, B = { 2, 2, 4 };        int N = A.Length;Â
        // Function Call        findWays(A, B, N);Â
        // Input 2        int[] A1 = { 1, 2, 3, 4 }, B1 = { 5, 6, 7, 8 };        int N1 = A1.Length;Â
        // Function Call        findWays(A1, B1, N1);    }} |
Javascript
// mod to avoid integer overflowconst mod = 1e9 + 7;Â
// dp tableconst dp = new Array(100001).fill(null).map(() => new Array(2).fill(-1));Â
// recursive Function to count ways to// form array of size N such that adjacent// elements chosen are differentfunction recur(i, j, Arr, N) {Â
  // If already computed state just  // return dp[i][j]  if (dp[i][j] !== -1) {    return dp[i][j];  }Â
  // If array of size N is possible  if (i === N) {    return 1;  }Â
  // Answer initialized with value zero  let ans = 0;Â
  // if choosing element from A[]  if (i === 0 || Arr[i - 1][j] !== Arr[i][0]) {    ans = (ans + recur(i + 1, 0, Arr, N)) % mod;  }Â
  // if choosing element from B[]  if (i === 0 || Arr[i - 1][j] !== Arr[i][1]) {    ans = (ans + recur(i + 1, 1, Arr, N)) % mod;  }Â
  // Return the final answer  return dp[i][j] = ans;}Â
// Function to count ways to form// array of size N such that adjacent// elements chosen are differentfunction findWays(A, B, N) {Â
  for(let i=0; i<100001; i++){      for(let j=0; j<2; j++)        dp[i][j]=-1;  }  // making one array for A[] & B[]  const Arr = new Array(N).fill(null).map((_, i) => [A[i], B[i]]);Â
  // calling recursive function  console.log(recur(0, 0, Arr, N));}Â
// Driver Code(function main() {Â
  // Input 1  const A = [1, 4, 3], B = [2, 2, 4];  const N = A.length;Â
  // Function Call  findWays(A, B, N);Â
  // Input 2  const A1 = [1, 2, 3, 4], B1 = [5, 6, 7, 8];  const N1 = A1.length;Â
  // Function Call  findWays(A1, B1, N1);Â
})(); |
Output
4 16
Time Complexity: O(N) Â
Auxiliary Space: O(N)
Related Articles:
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!
