Given array A[] of size N, array B[] of size M, and integer X, the task for this problem is to tell whether number X is possible to form or not if any number from array A[] is added to any number of times stepwise and in each step sum of number should not be equal to any number from B[]. Print “Yes” if possible else “No”.
Examples:
Input: A[] = {3, 4, 5}, B[] = {4, 5, 6, 8}, X = 15
Output: Yes
Explanation: Initially, we have a current value of zero let’s say curVal = 0
- Step 1 : Add A[0] = 3 in current value, curVal = 3 and B[] does not have 3 so move is valid
- Step 2 : Add A[1] = 4 in current value, curVal = 7 and B[] does not have 7 so move is valid
- Step 3 : Add A[2] = 5 in current value, curVal = 12 and B[] does not have 12 so move is valid
- Step 4 : Add A[0] = 3 in current value, curVal = 15 and B[] does not have 15 so move is valid
So 15 is possible to print “Yes”.
Input: A[] = {2, 3, 4, 5}, B[] = {3, 4, 5, 6}, X = 8
Output: No
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(XN)
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] represents whether i is possible or not from any combination.
- 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.
Recursion Tree of the first example.
- Green is a valid move whereas red is an invalid move.
- This is observed that at 11 and 12 same sub-tree is repeated as that part is already calculated simply return that part without calculating again (that is simply returning calculated values of repeated states).
Recursion Tree of the first example
Follow the steps below to solve the problem:
- Create HashMap[] and mark all values from B[] as 1 in HashMap[].
- Create a recursive function that takes one parameter i which represents the current value.
- Call the recursive function for choosing all numbers from A[].
- Base case if the current value is X return 1.
- Create a 1d array of dp[100001] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i].
- If the answer for a particular state is already computed then just return dp[i].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// DP table initialized with -1int dp[100001];// Recursive Function to tell whether X// is possible or notint recur(int i, int A[], int N, vector<int>& HashMap, int X){ // Base case if (i == X) { return 1; } // Initializing ans to 0, false value int ans = 0; // Calling recursive function for all // possible moves for (int j = 0; j < N; j++) { // Call function if (i + A[j] <= X and !HashMap[i + A[j]]) ans |= recur(i + A[j], A, N, HashMap, X); } // Save and return dp value return dp[i] = ans;}// Function to tell whether X is// possible or notvoid isPossible(int A[], int B[], int N, int M, int X){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // Creating HashMap vector<int> HashMap(100001, 0); // Marking all the B's which are // present in HashMap[] for (int i = 0; i < M; i++) { // B[i] exists HashMap[B[i]] = 1; } // Calling recursive function for // finding answer int ans = recur(0, A, N, HashMap, X); // If ans is 1 then if (ans) cout << "Yes" << endl; // Else else cout << "No" << endl;}// Driver Codeint main(){ // Input 1 int A1[] = { 3, 4, 5 }, B1[] = { 4, 5, 6, 8 }, X1 = 15; int N1 = sizeof(A1) / sizeof(A1[0]); int M1 = sizeof(B1) / sizeof(B1[0]); // Function Call isPossible(A1, B1, N1, M1, X1); // Input 2 int A2[] = { 2, 3, 4, 5 }, B2[] = { 3, 4, 5, 6 }, X2 = 8; int N2 = sizeof(A2) / sizeof(A2[0]); int M2 = sizeof(B2) / sizeof(B2[0]); // Function Call isPossible(A2, B2, N2, M2, X2); return 0;} |
Java
import java.util.*;public class Main { // Recursive Function to tell whether X // is possible or not public static int recur(int i, int[] A, int N, int[] HashMap, int X, int[] dp) { // Base case if (i == X) { return 1; } // Check if value is already calculated if (dp[i] != -1) { return dp[i]; } // Initializing ans to 0, false value int ans = 0; // Calling recursive function for all possible moves for (int j = 0; j < N; j++) { // Call function if (i + A[j] <= X && HashMap[i + A[j]] == 0) { ans |= recur(i + A[j], A, N, HashMap, X, dp); } } // Save and return dp value dp[i] = ans; return ans; } // Function to tell whether X is possible or not public static void isPossible(int[] A, int[] B, int N, int M, int X) { // Initializing dp array with - 1 int[] dp = new int[X + 1]; Arrays.fill(dp, -1); // Creating HashMap int[] HashMap = new int[100001]; // Marking all the B's which are present in HashMap[] for (int i = 0; i < M; i++) { // B[i] exists HashMap[B[i]] = 1; } // Calling recursive function for finding answer int ans = recur(0, A, N, HashMap, X, dp); // If ans is 1 then if (ans == 1) { System.out.println("Yes"); } // Else else { System.out.println("No"); } } // Driver Code public static void main(String[] args) { // Input 1 int[] A1 = {3, 4, 5}; int[] B1 = {4, 5, 6, 8}; int X1 = 15; int N1 = A1.length; int M1 = B1.length; // Function Call isPossible(A1, B1, N1, M1, X1); // Input 2 int[] A2 = {2, 3, 4, 5}; int[] B2 = {3, 4, 5, 6}; int X2 = 8; int N2 = A2.length; int M2 = B2.length; // Function Call isPossible(A2, B2, N2, M2, X2); }} |
Python3
# Python code to implement the approach# Recursive Function to tell whether X# is possible or notdef recur(i, A, N, HashMap, X, dp): # Base case if i == X: return 1 # Check if value is already calculated if dp[i] != -1: return dp[i] # Initializing ans to 0, false value ans = 0 # Calling recursive function for all # possible moves for j in range(N): # Call function if i + A[j] <= X and not HashMap[i + A[j]]: ans |= recur(i + A[j], A, N, HashMap, X, dp) # Save and return dp value dp[i] = ans return ans# Function to tell whether X is# possible or notdef isPossible(A, B, N, M, X): # Initializing dp array with - 1 dp = [-1] * (X+1) # Creating HashMap HashMap = [0] * (100001) # Marking all the B's which are # present in HashMap[] for i in range(M): # B[i] exists HashMap[B[i]] = 1 # Calling recursive function for # finding answer ans = recur(0, A, N, HashMap, X, dp) # If ans is 1 then if ans: print("Yes") # Else else: print("No")# Driver Codeif __name__ == '__main__': # Input 1 A1 = [3, 4, 5] B1 = [4, 5, 6, 8] X1 = 15 N1 = len(A1) M1 = len(B1) # Function Call isPossible(A1, B1, N1, M1, X1) # Input 2 A2 = [2, 3, 4, 5] B2 = [3, 4, 5, 6] X2 = 8 N2 = len(A2) M2 = len(B2) # Function Call isPossible(A2, B2, N2, M2, X2) |
Javascript
// JavaScript code to implement the approach// Recursive Function to tell whether X// is possible or notfunction recur(i, A, N, HashMap, X, dp) { // Base case if (i == X) { return 1; } // Check if value is already calculated if (dp[i] != -1) { return dp[i]; } // Initializing ans to 0, false value let ans = 0; // Calling recursive function for all // possible moves for (let j = 0; j < N; j++) { // Call function if (i + A[j] <= X && !HashMap[i + A[j]]) { ans |= recur(i + A[j], A, N, HashMap, X, dp); } } // Save and return dp value dp[i] = ans; return ans;}// Function to tell whether X is// possible or notfunction isPossible(A, B, N, M, X) { // Initializing dp array with - 1 let dp = new Array(X + 1).fill(-1); // Creating HashMap let HashMap = new Array(100001).fill(0); // Marking all the B's which are // present in HashMap[] for (let i = 0; i < M; i++) { // B[i] exists HashMap[B[i]] = 1; } // Calling recursive function for // finding answer let ans = recur(0, A, N, HashMap, X, dp); // If ans is 1 then if (ans) { console.log("Yes"); } // Else else { console.log("No"); }}// Driver Code// Input 1let A1 = [3, 4, 5];let B1 = [4, 5, 6, 8];let X1 = 15;let N1 = A1.length;let M1 = B1.length;// Function CallisPossible(A1, B1, N1, M1, X1);// Input 2let A2 = [2, 3, 4, 5];let B2 = [3, 4, 5, 6];let X2 = 8;let N2 = A2.length;let M2 = B2.length;// Function CallisPossible(A2, B2, N2, M2, X2);// This code is contributed by prasad264 |
C#
// C# code to implement the approachusing System;public class GFG { // DP table initialized with -1 static int[] dp = new int[100001]; // Recursive Function to tell whether X // is possible or not static int Recur(int i, int[] A, int N, int[] HashMap, int X) { // Base case if (i == X) return 1; // Initializing ans to 0, false value int ans = 0; // Calling recursive function for all // possible moves for (int j = 0; j < N; j++) { // Call function if (i + A[j] <= X && HashMap[i + A[j]] == 0) ans |= Recur(i + A[j], A, N, HashMap, X); } // Save and return dp value return dp[i] = ans; } // Function to tell whether X is // possible or not static void IsPossible(int[] A, int[] B, int N, int M, int X) { // Initializing dp array with -1 Array.Fill(dp, -1); // Creating HashMap int[] HashMap = new int[100001]; // Marking all the B's which are // present in HashMap[] for (int i = 0; i < M; i++) { // B[i] exists HashMap[B[i]] = 1; } // Calling recursive function for // finding answer int ans = Recur(0, A, N, HashMap, X); // If ans is 1 then if (ans == 1) Console.WriteLine("Yes"); // Else else Console.WriteLine("No"); } // Driver Code public static void Main() { // Input 1 int[] A1 = { 3, 4, 5 }; int[] B1 = { 4, 5, 6, 8 }; int X1 = 15; int N1 = A1.Length; int M1 = B1.Length; // Function Call IsPossible(A1, B1, N1, M1, X1); // Input 2 int[] A2 = { 2, 3, 4, 5 }; int[] B2 = { 3, 4, 5, 6 }; int X2 = 8; int N2 = A2.Length; int M2 = B2.Length; // Function Call IsPossible(A2, B2, N2, M2, X2); }} |
Output
Yes No
Time Complexity: O(N * X)
Auxiliary Space: O(X)
Share your thoughts in the comments
