Given numbers T, A, and B, the task is to find the greatest number less than equal to T formed by the sum of any combination of A and B (A and B can be used any number of times) along with one special operation that is at any instance sum can be halved (integer division by 2) by its current value at most one time.
Examples:
Input: T = 8, A = 5, B = 6
Output: 8
Explanation: There are two ways to reach the maximum value 8first way:
- Step 1: Choose 5 to add. the sum becomes 5.
- Step 2: Use special move and halve sum, sum becomes 2 (5÷2 == 2 as this is integer division).
- Step 3: Choose 6 to add, and the sum becomes 8.
second way:
- Step 1: Choose 6 to add. the sum becomes 6.
- Step 2: Use a special move and halve sum, sum becomes 3 (6÷2 == 3).
- Step 3: Choose 5 to add, and the sum becomes 8.
8 is the maximum sum possible less than equal to T = 8
Input: T = 11, A = 5, B = 8
Output: 10There is only one way to reach maximum value11
- Step 1: Choose 5 to add, Sum becomes 5.
- Step 2: Choose again 5 to add, Sum becomes 10.
10 is the maximum sum possible less than equal to T = 11
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: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
- dp[i][j] represents maximum sum less than equal to T with j special operations left.
- recurrence relation: dp[i][j] = max(dp[i – A][j], dp[i – B][j]) = dp[i / 2][0]
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 i representing the current sum and j representing the number of special operations left to perform.
- Call recursive function for both choosing A into sum and choosing B into sum.
- Create a 2d array of dp[N][2] with initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
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[1000001][2];// Recursive Function to calculate maximum// sum less than equal to T can be achieved// by adding numbers A or B repeatedlyint recur(int i, int j, int T, int A, int B){ // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; int ans = INT_MIN; // Calling recursive function for // adding A if (i + A <= T) ans = max(ans, recur(i + A, j, T, A, B)); // Else return value i else ans = i; // Calling recursive function for // adding B if (i + B <= T) ans = max(ans, recur(i + B, j, T, A, B)); // Else return value ans = max(ans, i) else ans = max(ans, i); // Calling recursive function for special // operation of halving current sum if (j == 1) ans = max(ans, recur(i / 2, 0, T, A, B)); // Save and return dp value return dp[i][j] = ans;}// Function to calculate maximum sum// less than equal to T can be achieved// by adding numbers A or B repeatedlyvoid maxTarLessThanEqualToT(int T, int A, int B){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); cout << recur(0, 1, T, A, B) << endl;}// Driver Codeint main(){ // Input 1 int T = 8, A = 5, B = 6; // Function Call maxTarLessThanEqualToT(T, A, B); // Input 2 int T1 = 11, A1 = 5, B1 = 8; // Function Call maxTarLessThanEqualToT(T1, A1, B1); return 0;} |
Python3
# Python code to implement the approach# DP table initialized with -1dp = [[-1 for i in range(2)] for j in range(1000001)]# Recursive Function to calculate maximum# sum less than equal to T can be achieved# by adding numbers A or B repeatedlydef recur(i, j, T, A, B): # If answer for current state is already # calculated then just return dp[i][j] if dp[i][j] != -1: return dp[i][j] ans = float('-inf') # Calling recursive function for # adding A if i + A <= T: ans = max(ans, recur(i + A, j, T, A, B)) # Else return value i else: ans = i # Calling recursive function for # adding B if i + B <= T: ans = max(ans, recur(i + B, j, T, A, B)) # Else return value ans = max(ans, i) else: ans = max(ans, i) # Calling recursive function for special # operation of halving current sum if j == 1: ans = max(ans, recur(i // 2, 0, T, A, B)) # Save and return dp value dp[i][j] = ans return ans# Function to calculate maximum sum# less than equal to T can be achieved# by adding numbers A or B repeatedlydef maxTarLessThanEqualToT(T, A, B): # Initializing dp array with - 1 for i in range(1000001): for j in range(2): dp[i][j] = -1 print(recur(0, 1, T, A, B))# Driver Codeif __name__ == '__main__': # Input 1 T = 8 A = 5 B = 6 # Function Call maxTarLessThanEqualToT(T, A, B) # Input 2 T1 = 11 A1 = 5 B1 = 8 # Function Call maxTarLessThanEqualToT(T1, A1, B1)# This code is contributed by shivamsharma215 |
C#
// C# code to implement the approachusing System;using System.Linq;using System.Collections.Generic;class GFG { // DP table initialized with -1 static int[,] dp=new int[1000001,2]; // Recursive Function to calculate maximum // sum less than equal to T can be achieved // by adding numbers A or B repeatedly static int recur(int i, int j, int T, int A, int B) { // If answer for current state is already // calculated then just return dp[i][j] if (dp[i,j] != -1) return dp[i,j]; int ans = Int32.MinValue; // Calling recursive function for // adding A if (i + A <= T) ans = Math.Max(ans, recur(i + A, j, T, A, B)); // Else return value i else ans = i; // Calling recursive function for // adding B if (i + B <= T) ans = Math.Max(ans, recur(i + B, j, T, A, B)); // Else return value ans = max(ans, i) else ans = Math.Max(ans, i); // Calling recursive function for special // operation of halving current sum if (j == 1) ans = Math.Max(ans, recur(i / 2, 0, T, A, B)); // Save and return dp value return dp[i,j] = ans; } // Function to calculate maximum sum // less than equal to T can be achieved // by adding numbers A or B repeatedly static void maxTarLessThanEqualToT(int T, int A, int B) { // Initializing dp array with - 1 for(int i=0; i<1000001; i++) for(int j=0; j<2; j++) dp[i,j]=-1; Console.WriteLine(recur(0, 1, T, A, B)); } // Driver Code static public void Main() { // Input 1 int T = 8, A = 5, B = 6; // Function Call maxTarLessThanEqualToT(T, A, B); // Input 2 int T1 = 11, A1 = 5, B1 = 8; // Function Call maxTarLessThanEqualToT(T1, A1, B1); } } |
Javascript
// Javascript code to implement the approach// DP table initialized with -1let dp=new Array(1000001);for(let i=0;i<1000001; i++) dp[i]=new Array(2);// Recursive Function to calculate maximum// sum less than equal to T can be achieved// by adding numbers A or B repeatedlyfunction recur(i, j, T, A, B){ // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; let ans = Number.MIN_SAFE_INTEGER; // Calling recursive function for // adding A if (i + A <= T) ans = Math.max(ans, recur(i + A, j, T, A, B)); // Else return value i else ans = i; // Calling recursive function for // adding B if (i + B <= T) ans = Math.max(ans, recur(i + B, j, T, A, B)); // Else return value ans = max(ans, i) else ans = Math.max(ans, i); // Calling recursive function for special // operation of halving current sum if (j == 1) ans = Math.max(ans, recur(Math.floor(i / 2), 0, T, A, B)); // Save and return dp value return dp[i][j] = ans;}// Function to calculate maximum sum// less than equal to T can be achieved// by adding numbers A or B repeatedlyfunction maxTarLessThanEqualToT(T, A, B){ // Initializing dp array with - 1 for(let i=0; i<1000001; i++) { for(let j=0; j<2; j++) dp[i][j]=-1; } console.log(recur(0, 1, T, A, B));}// Driver Code// Input 1let T = 8, A = 5, B = 6;// Function CallmaxTarLessThanEqualToT(T, A, B);// Input 2let T1 = 11, A1 = 5, B1 = 8;// Function CallmaxTarLessThanEqualToT(T1, A1, B1); |
Java
// Java code to implement the approachimport java.io.*;class GFG { // DP table initialized with -1 static int[][] dp = new int[1000001][2]; // Recursive Function to calculate maximum // sum less than equal to T can be achieved // by adding numbers A or B repeatedly static int recur(int i, int j, int T, int A, int B) { // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; int ans = Integer.MIN_VALUE; // Calling recursive function for // adding A if (i + A <= T) ans = Math.max(ans, recur(i + A, j, T, A, B)); // Else return value i else ans = i; // Calling recursive function for // adding B if (i + B <= T) ans = Math.max(ans, recur(i + B, j, T, A, B)); // Else return value ans = max(ans, i) else ans = Math.max(ans, i); // Calling recursive function for special // operation of halving current sum if (j == 1) ans = Math.max(ans, recur(i / 2, 0, T, A, B)); // Save and return dp value return dp[i][j] = ans; } // Function to calculate maximum sum // less than equal to T can be achieved // by adding numbers A or B repeatedly static void maxTarLessThanEqualToT(int T, int A, int B) { // Initializing dp array with - 1 for(int i=0; i<1000001; i++) for(int j=0; j<2; j++) dp[i][j]=-1; System.out.println(recur(0, 1, T, A, B)); } // Driver Code public static void main (String[] args) { // Input 1 int T = 8, A = 5, B = 6; // Function Call maxTarLessThanEqualToT(T, A, B); // Input 2 int T1 = 11, A1 = 5, B1 = 8; // Function Call maxTarLessThanEqualToT(T1, A1, B1); }} |
Output
8 10
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!
Share your thoughts in the comments
