Minimum cost to reduce given number to less than equal to zero

19 June 2025

2

Given array A[] and B[] of size N representing N type of operations. Given a number H, reduce this number to less than equal to 0 by performing the following operation at minimum cost. Choose i^th operation and subtract A[i] from H and the cost incurred will be B[i]. Every operation can be performed any number of times.

Examples:

Input: A[] = {8, 4, 2}, B[] = {3, 2, 1}, H = 9
Output: 4
Explanation: The optimal way to solve this problem is to decrease the number H = 9 by the first operation reducing it by A[1] = 8 and the cost incurred is B[1] = 3. H is now 1. Use the third operation to reduce H = 1 by A[3] = 2 cost incurred will be B[3] = 1. Now H is -1 which is less than equal to 0 hence. in cost = 3 + 1 = 4 number H can be made less than equal to 0.

Input: A[] = {1, 2, 3, 4, 5, 6}, B[] = {1, 3, 9, 27, 81, 243}, H = 100
Output: 100
Explanation: It is optimal to use the first operation 100 times to make H zero in minimum cost.

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

Another approach : Recursive + Memoization

In this approach we find our answer with the help of recursion but to avoid recomputing of same problem we use use a vector memo to store the computations of subproblems.

Implementation :

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost to make
// number H less than or equal to zero
int findMinimumCost(int A[], int B[], int N, int H,
                    vector<int>& memo)
{
 
    // base case
    if (H <= 0) {
        return 0;
    }
 
    // check if the result is already computed
    if (memo[H] != -1) {
        return memo[H];
    }
 
    int ans = INT_MAX;
    // recursive step
    for (int i = 0; i < N; i++) {
        ans = min(ans,
                  findMinimumCost(A, B, N, H - A[i], memo)
                      + B[i]);
    }
 
    // store the computed result in memo table
    memo[H] = ans;
 
    return ans;
}
 
// Driver Code
int main()
{
    // Test Case 1
    int A[] = { 8, 4, 2 }, B[] = { 3, 2, 1 }, H = 9;
    int N = sizeof(A) / sizeof(A[0]);
 
    // Memo table to store the computed results
    vector<int> memo(H + 1, -1);
 
    // Function Call
    cout << findMinimumCost(A, B, N, H, memo) << endl;
 
    // Test Case 2
    int A1[] = { 1, 2, 3, 4, 5, 6 },
        B1[] = { 1, 3, 9, 27, 81, 243 }, H1 = 100;
    int N1 = sizeof(A1) / sizeof(A1[0]);
 
    // Memo table to store the computed results
    vector<int> memo1(H1 + 1, -1);
 
    // Function Call
    cout << findMinimumCost(A1, B1, N1, H1, memo1) << endl;
 
    return 0;
}

Java

import java.util.Arrays;
 
public class GFG {
 
    // Function to find the minimum cost to make
    // number H less than or equal to zero
    public static int findMinimumCost(int[] A, int[] B,
                                      int N, int H,
                                      int[] memo)
    {
 
        // base case
        if (H <= 0) {
            return 0;
        }
 
        // check if the result is already computed
        if (memo[H] != -1) {
            return memo[H];
        }
 
        int ans = Integer.MAX_VALUE;
        // recursive step
        for (int i = 0; i < N; i++) {
            ans = Math.min(ans, findMinimumCost(
                                    A, B, N, H - A[i], memo)
                                    + B[i]);
        }
 
        // store the computed result in memo table
        memo[H] = ans;
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Test Case 1
        int[] A = { 8, 4, 2 };
        int[] B = { 3, 2, 1 };
        int H = 9;
        int N = A.length;
 
        // Memo table to store the computed results
        int[] memo = new int[H + 1];
        Arrays.fill(memo, -1);
 
        // Function Call
        System.out.println(
            findMinimumCost(A, B, N, H, memo));
 
        // Test Case 2
        int[] A1 = { 1, 2, 3, 4, 5, 6 };
        int[] B1 = { 1, 3, 9, 27, 81, 243 };
        int H1 = 100;
        int N1 = A1.length;
 
        // Memo table to store the computed results
        int[] memo1 = new int[H1 + 1];
        Arrays.fill(memo1, -1);
 
        // Function Call
        System.out.println(
            findMinimumCost(A1, B1, N1, H1, memo1));
    }
}

Python

# Function to find the minimum cost to make
# number H less than or equal to zero
def findMinimumCost(A, B, N, H, memo):
    # Base case
    if H <= 0:
        return 0
 
    # Check if the result is already computed
    if memo[H] != -1:
        return memo[H]
 
    ans = float('inf')
    # Recursive step
    for i in range(N):
        ans = min(ans, findMinimumCost(A, B, N, H - A[i], memo) + B[i])
 
    # Store the computed result in memo table
    memo[H] = ans
 
    return ans
 
# Driver Code
if __name__ == "__main__":
    # Test Case 1
    A = [8, 4, 2]
    B = [3, 2, 1]
    H = 9
    N = len(A)
 
    # Memo table to store the computed results
    memo = [-1] * (H + 1)
 
    # Function Call
    print(findMinimumCost(A, B, N, H, memo))
 
    # Test Case 2
    A1 = [1, 2, 3, 4, 5, 6]
    B1 = [1, 3, 9, 27, 81, 243]
    H1 = 100
    N1 = len(A1)
 
    # Memo table to store the computed results
    memo1 = [-1] * (H1 + 1)
 
    # Function Call
    print(findMinimumCost(A1, B1, N1, H1, memo1))

C#

using System;
using System.Collections.Generic;
 
class Gfg
{
    // Function to find the minimum cost to make
    // number H less than or equal to zero
    static int findMinimumCost(int[] A, int[] B, int N, int H, List<int> memo)
    {
        // Base case
        if (H <= 0)
        {
            return 0;
        }
 
        // Check if the result is already computed
        if (memo[H] != -1)
        {
            return memo[H];
        }
 
        int ans = int.MaxValue;
        // Recursive step
        for (int i = 0; i < N; i++)
        {
            ans = Math.Min(ans, findMinimumCost(A, B, N, H - A[i], memo) + B[i]);
        }
 
        // Store the computed result in the memo table
        memo[H] = ans;
 
        return ans;
    }
 
    static void Main(string[] args)
    {
        // Test Case 1
        int[] A = { 8, 4, 2 };
        int[] B = { 3, 2, 1 };
        int H = 9;
        int N = A.Length;
 
        // Memo table to store the computed results
        List<int> memo = new List<int>(new int[H + 1]);
        for (int i = 0; i <= H; i++)
        {
            memo[i] = -1;
        }
 
        // Function Call
        Console.WriteLine(findMinimumCost(A, B, N, H, memo));
 
        // Test Case 2
        int[] A1 = { 1, 2, 3, 4, 5, 6 };
        int[] B1 = { 1, 3, 9, 27, 81, 243 };
        int H1 = 100;
        int N1 = A1.Length;
 
        // Memo table to store the computed results
        List<int> memo1 = new List<int>(new int[H1 + 1]);
        for (int i = 0; i <= H1; i++)
        {
            memo1[i] = -1;
        }
 
        // Function Call
        Console.WriteLine(findMinimumCost(A1, B1, N1, H1, memo1));
    }
}

Javascript

// Function to find the minimum cost to make
// number H less than or equal to zero
function findMinimumCost(A, B, N, H, memo)
{
 
    // base case
    if (H <= 0) {
        return 0;
    }
 
    // check if the result is already computed
    if (memo[H] != -1) {
        return memo[H];
    }
 
    let ans = Number.MAX_VALUE;
    // recursive step
    for (let i = 0; i < N; i++) {
        ans = Math.min(ans,
                  findMinimumCost(A, B, N, H - A[i], memo)
                      + B[i]);
    }
 
    // store the computed result in memo table
    memo[H] = ans;
 
    return ans;
}
 
// Test Case 1
let A = [ 8, 4, 2 ], B = [ 3, 2, 1 ], H = 9;
let N = A.length;
 
// Memo table to store the computed results
let memo=new Array(H + 1).fill(-1);
 
// Function Call
console.log(findMinimumCost(A, B, N, H, memo));
 
// Test Case 2
let A1 = [ 1, 2, 3, 4, 5, 6 ], B1 = [ 1, 3, 9, 27, 81, 243 ], H1 = 100;
let N1 = A1.length;
 
// Memo table to store the computed results
let memo1=new Array(H1 + 1).fill(-1);
 
// Function Call
console.log(findMinimumCost(A1, B1, N1, H1, memo1));

Output

4
100

Time Complexity: O(N * H)
Auxiliary Space: O(H)

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

Dynamic programming can be used to solve this problem

dp[i] represents a minimum cost to make I zero from given operations

recurrence relation: dp[i] = min(dp[i], dp[max(0, i – A[i])] + B[i])

Follow the steps below to solve the problem:

Declare a dp table of size H + 1 with all values initialized to infinity
Base case dp[0] = 0
Iterate from 1 to H to calculate a value for each of them and to do that use all operations from 0 to j and try to make i zero by the minimum cost of these operations.
Finally, return minimum cost dp[H]

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Minimum cost to make number H
// less than equal to zero
int findMinimumCost(int A[], int B[], int N, int H)
{
 
    // Declaring dp array initially all values
    // infinity
    vector<int> dp(H + 1, INT_MAX);
 
    // base case
    dp[0] = 0;
 
    // Calculating minimum cost for each i
    // from 1 to H
    for (int i = 1; i <= H; i++) {
 
        for (int j = 0; j < N; j++) {
            dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j]);
        }
    }
 
    // Returning the answer
    return dp[H];
}
 
// Driver Code
int main()
{
    // Test Case 1
    int A[] = { 8, 4, 2 }, B[] = { 3, 2, 1 }, H = 9;
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    cout << findMinimumCost(A, B, N, H) << endl;
 
    // Test Case 2
    int A1[] = { 1, 2, 3, 4, 5, 6 },
        B1[] = { 1, 3, 9, 27, 81, 243 }, H1 = 100;
    int N1 = sizeof(A1) / sizeof(A1[0]);
 
    // Function Call
    cout << findMinimumCost(A1, B1, N1, H1) << endl;
 
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
 
class GFG {
    // Minimum cost to make number H
    // less than equal to zero
    public static int findMinimumCost(int A[], int B[],
                                      int N, int H)
    {
 
        // Declaring dp array initially all values
        // infinity
        int dp[] = new int[H + 1];
        for (int i = 0; i < H + 1; i++)
            dp[i] = Integer.MAX_VALUE;
 
        // base case
        dp[0] = 0;
 
        // Calculating minimum cost for each i
        // from 1 to H
        for (int i = 1; i <= H; i++) {
 
            for (int j = 0; j < N; j++) {
                int x = Math.max(0, i - A[j]);
                dp[i] = Math.min(dp[i],
                                 dp[x]
                                     + B[j]);
            }
        }
 
        // Returning the answer
        return dp[H];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Test Case 1
        int A[] = { 8, 4, 2 }, B[] = { 3, 2, 1 }, H = 9;
        int N = A.length;
 
        // Function Call
        System.out.println(findMinimumCost(A, B, N, H));
 
        // Test Case 2
        int A1[] = { 1, 2, 3, 4, 5, 6 },
            B1[] = { 1, 3, 9, 27, 81, 243 }, H1 = 100;
        int N1 = A1.length;
 
        // Function Call
        System.out.println(findMinimumCost(A1, B1, N1, H1));
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code to implement the approach
import sys
 
# Minimum cost to make number H
# less than equal to zero
def findMinimumCost(A, B, N, H):
    # Declaring dp array initially all values
    # infinity
    dp =[sys.maxsize]*(H + 1)
     
    # base case
    dp[0]= 0
     
    # Calculating minimum cost for each i
    # from 1 to H
    for i in range(1, H + 1):
        for j in range(N):
            dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j])
             
    # Returning the answer
    return dp[H]
     
# Driver Code
 
# Test Case 1
A =[8, 4, 2]
B =[3, 2, 1]
H = 9
 
N = len(A)
 
# Function Call
print(findMinimumCost(A, B, N, H))
 
# Test Case 2
A1 =[1, 2, 3, 4, 5, 6]
B1 =[1, 3, 9, 27, 81, 243]
H1 = 100
 
N1 = len(A)
 
# Function Call
print(findMinimumCost(A1, B1, N1, H1))
 
# This code is contributed by Pushpesh Raj.

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
public class Gfg {
 
    // Minimum cost to make number H
    // less than equal to zero
    static int findMinimumCost(int[] A, int[] B, int N, int H)
    {
 
        // Declaring dp array initially all values
        // infinity
        // vector<int> dp(H + 1, INT_MAX);
        int[] dp = new int[H + 1];
        for (int i = 0; i < H + 1; i++)
            dp[i] = 2147483647;
        // base case
        dp[0] = 0;
 
        // Calculating minimum cost for each i
        // from 1 to H
        for (int i = 1; i <= H; i++) {
 
            for (int j = 0; j < N; j++) {
                int x = Math.Max(0, i - A[j]);
                dp[i] = Math.Min(dp[i], dp[x] + B[j]);
            }
        }
 
        // Returning the answer
        return dp[H];
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // Test Case 1
        int[] A = { 8, 4, 2 };
        int[] B = { 3, 2, 1 };
        int H = 9;
        int N = A.Length;
 
        // Function Call
        Console.WriteLine(findMinimumCost(A, B, N, H));
 
        // Test Case 2
        int[] A1 = { 1, 2, 3, 4, 5, 6 };
        int[] B1 = { 1, 3, 9, 27, 81, 243 };
        int H1 = 100;
        int N1 = A1.Length;
 
        // Function Call
        Console.WriteLine(findMinimumCost(A1, B1, N1, H1));
    }
}
 
// This code is contributed by poojaagarwal2.

Javascript

  // JS code to implement the approach
 
  // Minimum cost to make number H
  // less than equal to zero
  function findMinimumCost(A, B, N, H) {
 
    // Declaring dp array initially all values
    // infinity
    let dp = new Array(H + 1).fill(Number.MAX_VALUE);
 
    // base case
    dp[0] = 0;
 
    // Calculating minimum cost for each i
    // from 1 to H
    for (let i = 1; i <= H; i++) {
 
      for (let j = 0; j < N; j++) {
        let x = Math.max(0, i - A[j]);
        dp[i] = Math.min(dp[i], dp[x] + B[j]);
      }
    }
 
    // Returning the answer
    return dp[H];
  }
 
  // Driver Code
 
  // Test Case 1
  let A = [8, 4, 2], B = [3, 2, 1], H = 9;
  let N = A.length;
 
  // Function Call
  console.log(findMinimumCost(A, B, N, H) + "<br>");
 
  // Test Case 2
  let A1 = [1, 2, 3, 4, 5, 6],
    B1 = [1, 3, 9, 27, 81, 243], H1 = 100;
  let N1 = A1.length;
 
  // Function Call
 console.log(findMinimumCost(A1, B1, N1, H1) + "<br>");
 
// This code is contributed by Potta Lokesh

Output

4
100

Time Complexity: O(N * H)
Auxiliary Space: O(N * H)

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!

Minimum cost to reduce given number to less than equal to zero

C++

Java

Python

C#

Javascript

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US