Select Minimum indices having sum in first and second Array at least X and Y - Coding

Given array A[] and B[] both having size N. Select minimum number indexes so that sum of elements from A[] on those indexes and the sum of elements of B[] on the same indexes are at least X and Y respectively. Print the count of the minimum number of indexes else if it is not possible print – 1.

Examples:

Input: A[] = {2, 3, 2}, B[] = {1, 4, 3}, X = 5, Y = 6
Output: 2
Explanation: Selecting the 2nd and 3rd index we will get the sum 3 + 2 = 5 in the first array and 4 + 3 = 7 in the second array. 5 ≥ X and 7 ≥ Y so both the conditions are true. Hence answer will be 2.

Input: A[] = {3, 2, 2}, B[] = {4, 3, 1}, X = 8, Y = 8
Output: -1
Explanation: Even if we select all the indexes then also the sum of the first array will never be greater than equal to X. Hence -1 will be the answer that is not possible

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(2^N)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized based on the following idea:

Dynamic programming can be used to solve this problem

Naive DP:

dp[i][j][k] represents the minimum number of indexes selected from the first i indexes so that sum of the first array on those indexes is equal to j and the second array on the same indexes is equal to k.

dp[i][j][k] = min(dp[i + 1][j + A[i]][k + B[i]] + 1, dp[i + 1][j][k]);

The problem with this DP approach is that we need to make a dp array of size about the total maximum sum of the first array and the total maximum sum of the second array which is not possible.

Optimized DP:

dp[i][j][k] represents the minimum number of indexes subtracted from the first array from X and the second array from Y so that they are both zero.

dp[i][j][k] = min(dp[i + 1][j – A[i]][k – B[i]] + 1, dp[i + 1][j][k]

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 using by store the value of a state and whenever the function is called, return the stored value without computing again.

Follow the steps below to solve the problem:

Create a recursive function that takes three parameters i representing the index that is to be chosen, j representing leftover X, and k representing leftover Y.
Call the recursive function for both choosing the current index and not choosing the current index.
Base case if both j and k are 0 then return 0 else return an invalid number.
Create a 3d array of dp[N][X][Y] initially filled with -1.
If the answer for a particular state is computed then save it in dp[i][j][k].
If the answer for a particular state is already computed then just return dp[i][j][k].

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 - 1
int dp[301][301][301];
 
// Recursive function to count minimum number
// of indexes selected such that their sum
// in array A is atleast X and in array B
// is atleast Y.
int recur(int i, int j, int k, int A[], int B[], int N)
{
    // Base case
    if (i == N) {
 
        // If both j and k becomes zero then
        // answer exists
        if (j == 0 and k == 0)
            return 0;
 
        // Else return invalid answer
        else
            return 1e9;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j][k] != -1)
        return dp[i][j][k];
 
    int ans = INT_MAX;
 
    // Calling recursive function for not taking
    // current index in answer
    ans = min(ans, recur(i + 1, j, k, A, B, N));
 
    // Calling recursive function for
    // taking current index in answer
    ans = min(ans, recur(i + 1, max(0, j - A[i]),
                         max(0, k - B[i]), A, B, N)
                       + 1);
 
    // Save and return dp value
    return dp[i][j][k] = ans;
}
 
// Function to count minimum number of
// indexes selected such that their sum in array A is
// atleast X and in array B is atleast Y.
int findMinimumCount(int A[], int B[], int N, int X, int Y)
{
    // Filling dp table with -1
    memset(dp, -1, sizeof(dp));
 
    // Calling recursive function
    int ans = recur(0, X, Y, A, B, N);
 
    // If answer does not exist return -1
    if (ans == 1e9)
        return -1;
    else
        return ans;
}
 
// Driver Code
int main()
{
    // Test Case 1
    int A[] = { 2, 3, 2 }, B[] = { 1, 4, 3 }, X = 5, Y = 6;
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << findMinimumCount(A, B, N, X, Y) << endl;
 
    // Test Case 2
    int A1[] = { 3, 2, 2 }, B1[] = { 4, 3, 1 }, X1 = 8,
        Y1 = 8;
    int N1 = sizeof(A1) / sizeof(A1[0]);
 
    // Function Call
    cout << findMinimumCount(A1, B1, N1, X1, Y1) << endl;
 
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.Arrays;
 
class GFG 
{
   
  // Dp table initialized with - 1
  static int dp[][][] = new int[301][301][301];
 
  // Recursive function to count minimum number
  // of indexes selected such that their sum
  // in array A is atleast X and in array B
  // is atleast Y.
  public static int recur(int i, int j, int k, int A[],
                          int B[], int N)
  {
    // Base case
    if (i == N) {
 
      // If both j and k becomes zero then
      // answer exists
      if (j == 0 && k == 0)
        return 0;
 
      // Else return invalid answer
      else
        return 1000000000;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j][k] != -1)
      return dp[i][j][k];
 
    int ans = Integer.MAX_VALUE;
 
    // Calling recursive function for not taking
    // current index in answer
    ans = Math.min(ans, recur(i + 1, j, k, A, B, N));
 
    // Calling recursive function for
    // taking current index in answer
    ans = Math.min(ans,
                   recur(i + 1, Math.max(0, j - A[i]),
                         Math.max(0, k - B[i]), A, B, N)
                   + 1);
 
    // Save and return dp value
    return dp[i][j][k] = ans;
  }
 
  // Function to count minimum number of
  // indexes selected such that their sum in array A is
  // atleast X and in array B is atleast Y.
  public static int findMinimumCount(int A[], int B[],
                                     int N, int X, int Y)
  {
    // Filling dp table with -1
    for (int[][] row : dp) {
      for (int[] rowColumn : row) {
        Arrays.fill(rowColumn, -1);
      }
    }
 
    // Calling recursive function
    int ans = recur(0, X, Y, A, B, N);
 
    // If answer does not exist return -1
    if (ans == 1000000000)
      return -1;
    else
      return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Test Case 1
    int A[] = { 2, 3, 2 };
    int B[] = { 1, 4, 3 };
    int X = 5;
    int Y = 6;
    int N = A.length;
 
    // Function Call
    System.out.println(findMinimumCount(A, B, N, X, Y));
 
    // Test Case 2
    int A1[] = { 3, 2, 2 };
    int B1[] = { 4, 3, 1 };
    int X1 = 8;
    int Y1 = 8;
    int N1 = A1.length;
 
    // Function Call
    System.out.println(
      findMinimumCount(A1, B1, N1, X1, Y1));
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code to implement the approach
import math
 
# Dp table initialized with - 1
dp = [[[-1 for _ in range(301)] for _ in range(301)] for _ in range(301)]
 
# Recursive function to count minimum number
# of indexes selected such that their sum
# in array A is atleast X and in array B
# is atleast Y.
def recur(i, j, k, A, B, N):
    # Base case
    if i == N:
        # If both j and k becomes zero then
        # answer exists
        if j == 0 and k == 0:
            return 0
        # Else return invalid answer
        else:
            return 1000000000
 
    # If answer for current state is already
    # calculated then just return dp[i][j]
    if dp[i][j][k] != -1:
        return dp[i][j][k]
 
    ans = math.inf
 
    # Calling recursive function for not taking
    # current index in answer
    ans = min(ans, recur(i + 1, j, k, A, B, N))
 
    # Calling recursive function for
    # taking current index in answer
    ans = min(ans, recur(i + 1, max(0, j - A[i]),
                         max(0, k - B[i]), A, B, N)
              + 1)
 
    # Save and return dp value
    dp[i][j][k] = ans
    return ans
 
# Function to count minimum number of
# indexes selected such that their sum in array A is
# atleast X and in array B is atleast Y.
def findMinimumCount(A, B, N, X, Y):
    # Calling recursive function
    ans = recur(0, X, Y, A, B, N)
 
    # If answer does not exist return -1
    if ans == 1000000000:
        return -1
    else:
        return ans
 
 
# Test Case 1
A = [2, 3, 2]
B = [1, 4, 3]
X = 5
Y = 6
N = len(A)
 
# Function Call
print(findMinimumCount(A, B, N, X, Y))
 
# Test Case 2
A1 = [3, 2, 2]
B1 = [4, 3, 1]
X1 = 8
Y1 = 8
N1 = len(A1)
 
# Function Call
print(findMinimumCount(A1, B1, N1, X1, Y1))
 
# This code is contributed by lokeshmvs21.

C#

// C# code to implement the approach
using System;
using System.Linq;
 
public class GFG {
 
  // Dp table initialized with - 1
  static int[, , ] dp = new int[301, 301, 301];
 
  // Recursive function to count minimum number
  // of indexes selected such that their sum
  // in array A is atleast X and in array B
  // is atleast Y.
  public static int recur(int i, int j, int k, int[] A,
                          int[] B, int N)
  {
    // Base case
    if (i == N) {
      // If both j and k becomes zero then
      // answer exists
      if (j == 0 && k == 0)
        return 0;
 
      // Else return invalid answer
      else
        return 1000000000;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i, j, k] != -1)
      return dp[i, j, k];
 
    int ans = int.MaxValue;
 
    // Calling recursive function for not taking
    // current index in answer
    ans = Math.Min(ans, recur(i + 1, j, k, A, B, N));
 
    // Calling recursive function for
    // taking current index in answer
    ans = Math.Min(ans,
                   recur(i + 1, Math.Max(0, j - A[i]),
                         Math.Max(0, k - B[i]), A, B, N)
                   + 1);
 
    // Save and return dp value
    return dp[i, j, k] = ans;
  }
 
  // Function to count minimum number of
  // indexes selected such that their sum in array A is
  // atleast X and in array B is atleast Y.
  public static int findMinimumCount(int[] A, int[] B,
                                     int N, int X, int Y)
  {
    // Filling dp table with -1
    for (int i = 0; i < dp.GetLength(0); i++) {
      for (int j = 0; j < dp.GetLength(1); j++) {
        for (int k = 0; k < dp.GetLength(2); k++) {
          dp[i, j, k] = -1;
        }
      }
    }
 
    // Calling recursive function
    int ans = recur(0, X, Y, A, B, N);
 
    // If answer does not exist return -1
    if (ans == 1000000000)
      return -1;
    else
      return ans;
  }
 
  static public void Main()
  {
 
    // Code
    // Test Case 1
    int[] A = { 2, 3, 2 };
    int[] B = { 1, 4, 3 };
    int X = 5;
    int Y = 6;
    int N = A.Length;
 
    // Function Call
    Console.WriteLine(findMinimumCount(A, B, N, X, Y));
 
    // Test Case 2
    int[] A1 = { 3, 2, 2 };
    int[] B1 = { 4, 3, 1 };
    int X1 = 8;
    int Y1 = 8;
    int N1 = A1.Length;
 
    // Function Call
    Console.WriteLine(
      findMinimumCount(A1, B1, N1, X1, Y1));
  }
}
 
// This code is contributed by lokesh.

Javascript

// Javascript code to implement the approach
 
// Dp table initialized with - 1
let dp = new Array(301);
 
for(let i=0; i<301; i++){
    dp[i]=new Array(301);
    for(let j=0; j<301; j++){
        dp[i][j]=new Array(301).fill(-1);
    }
}
// Recursive function to count minimum number
// of indexes selected such that their sum
// in array A is atleast X and in array B
// is atleast Y.
function recur(i, j, k, A, B, N)
{
    // Base case
    if (i == N) {
 
        // If both j and k becomes zero then
        // answer exists
        if (j == 0 && k == 0)
            return 0;
 
        // Else return invalid answer
        else
            return 1e9;
    }
 
    // If answer for current state is already
    // calculated then just return dp[i][j]
    if (dp[i][j][k] != -1)
        return dp[i][j][k];
 
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Calling recursive function for not taking
    // current index in answer
    ans = Math.min(ans, recur(i + 1, j, k, A, B, N));
 
    // Calling recursive function for
    // taking current index in answer
    ans = Math.min(ans, recur(i + 1, Math.max(0, j - A[i]),
                         Math.max(0, k - B[i]), A, B, N)
                       + 1);
 
    // Save and return dp value
    return dp[i][j][k] = ans;
}
 
// Function to count minimum number of
// indexes selected such that their sum in array A is
// atleast X and in array B is atleast Y.
function findMinimumCount(A, B, N, X, Y)
{
    // Filling dp table with -1
    
    // Calling recursive function
    let ans = recur(0, X, Y, A, B, N);
 
    // If answer does not exist return -1
    if (ans == 1e9)
        return -1;
    else
        return ans;
}
 
// Driver Code
    // Test Case 1
    let A = [2, 3, 2], B = [ 1, 4, 3 ], X = 5, Y = 6;
    let N = A.length;
 
    // Function Call
    document.write(findMinimumCount(A, B, N, X, Y));
     
    document.write("<br>");
 
    // Test Case 2
    let A1 = [ 3, 2, 2 ], B1 = [4, 3, 1], X1 = 8, Y1 = 8;
    let N1 = A1.length;
 
    // Function Call
    document.write(findMinimumCount(A1, B1, N1, X1, Y1))

Output

2
-1

Time Complexity: O(N * X * Y)
Auxiliary Space: O(N * X * Y)

Related Articles:

Reffered: https://www.geeksforgeeks.org

DSA

Related
Minimum cost to reduce given number to less than equal to zero
Minimum operations required to Sort the Array using following operations
Implementation of Wu Manber Algorithm?
Maximum non overlapping Subset with sum greater than K
Check if given Array can be formed by increasing or decreasing element

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	9