Given an integer N, the task is to find the maximum value of function F(n) given by F(N) = max(N, F(N /2) + F(N / 3) + F(N / 4)).
Examples:
Input: N = 3
Output: 3
Explanation:
F(3) = max(3, F(1) + F(1) + F(0)) as F(0) = 0 and F(1) = 1
F(3) = max(3, 1 + 1+ 0)
F(3) = max(3, 2)
Hence, the maximum value of F(3) is 3.Input: N = 12
Output:13
Explanation:
F(12) = max(12, F(6) + F(4) + F(3))
F(6) = max(6, F(3) + F(2) + F(1))
F(3) = max(3, F(1) + F(1) + F(0)) as F(0) = 0 and F(1) = 1
F(3) = max(3, 1 + 1+ 0)
F(3) = max(3, 2) = 3
F(2) = max(2, F(1) + F(0) + F(0))
F(2) = max(2,1 + 0 + 0) = 2
F(4) = max(4, F(2) + F(1) + F(1))
F(4) = max(4, 2 + 1 + 1) = 4
F(6) = max(6, 3 + 2 + 1) = 6
Now, F(12) = max(12, 6 + 4 + 3)
F(12) = max(12, 13)
Hence, the maximum value of F(12) is 13.
Naive Approach: The simplest approach is to use recursion to calculate the value of F(N). In each step, call three recursive calls for each of the values N/2, N/3, and N/4, and then each recursive call returns the value of the maximum of N and the sum of values returned by these recursive calls. After all, the recursive call ends print the value as the result.
Time Complexity: O(3N)
Auxiliary Space: O(1)
Dynamic Programming using Bottom-Down Approach: The recursive calls in the above can also be reduced using an auxiliary array dp[] and calculate the value of each state in the bottom-up approach. Below are the steps:
- Create an auxiliary array dp[] of size N.
- Initialize the state 0 and 1 as dp[0] = 0 and dp[1] = 1.
- Traverse the array dp[] over the range [2, N] and update each state as:
dp[i] = max(i, dp[i/2] + dp[i/3] + dp[i/4])
- Print the value of dp[N] after the above steps as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to build the auxiliary DP // array from the start void build(int dp[], int N) { // Base Case dp[0] = 0; dp[1] = 1; // Iterate over the range for (int i = 2; i <= N; i++) { // Update each state dp[i] = max(i, dp[i / 2] + dp[i / 3] + dp[i / 4]); } } // Function to find the maximum value of // F(n) = max(n, F[n/2] + F[n/3] + F[n/4]) int maxValue(int N) { // Auxuliary DP array int dp[N + 1]; // Function call to build DP array build(dp, N); // Print the answer cout << dp[N]; } // Driver Code int main() { // Given N int N = 12; // Function Call maxValue(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to build the auxiliary DP // array from the start static void build(int dp[], int N) { // Base Case dp[0] = 0; dp[1] = 1; // Iterate over the range for(int i = 2; i <= N; i++) { // Update each state dp[i] = Math.max(i, dp[i / 2] + dp[i / 3] + dp[i / 4]); } } // Function to find the maximum value of // F(n) = max(n, F[n/2] + F[n/3] + F[n/4]) static void maxValue(int N) { // Auxuliary DP array int dp[] = new int[N + 1]; // Function call to build DP array build(dp, N); // Print the answer System.out.println(dp[N]); } // Driver code public static void main(String[] args) { // Given N int N = 12; // Function Call maxValue(N); } } // This code is contributed by code_hunt |
Python3
# Python3 program for the above approach # Function to build the auxiliary DP # array from the start def build(dp, N): # Base Case dp[0] = 0 dp[1] = 1 # Iterate over the range for i in range(2, N + 1): # Update each state dp[i] = max(i, dp[i // 2] + dp[i // 3] + dp[i // 4]) # Function to find the maximum value of # F(n) = max(n, F[n/2] + F[n/3] + F[n/4]) def maxValue(N): # Auxuliary DP array dp = [0] * (N + 1) # Function call to build DP array build(dp, N) # Print the answer print(dp[N], end = "") # Driver Code if __name__ == '__main__': # Given N N = 12 # Function Call maxValue(N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; class GFG{ // Function to build the // auxiliary DP array // from the start static void build(int []dp, int N) { // Base Case dp[0] = 0; dp[1] = 1; // Iterate over the range for(int i = 2; i <= N; i++) { // Update each state dp[i] = Math.Max(i, dp[i / 2] + dp[i / 3] + dp[i / 4]); } } // Function to find the // maximum value of F(n) = // max(n, F[n/2] + F[n/3] + F[n/4]) static void maxValue(int N) { // Auxuliary DP array int []dp = new int[N + 1]; // Function call to // build DP array build(dp, N); // Print the answer Console.WriteLine(dp[N]); } // Driver code public static void Main(String[] args) { // Given N int N = 12; // Function Call maxValue(N); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript program for the // above approach // Function to build the // auxiliary DP array // from the start function build( dp, N) { // Base Case dp[0] = 0; dp[1] = 1; // Iterate over the range for(var i = 2; i <= N; i++) { // Update each state dp[i] = Math.max(i, dp[(Math.floor(i / 2))] + dp[(Math.floor(i / 3))] + dp[(Math.floor(i / 4))]); } } // Function to find the // maximum value of F(n) = // max(n, F[n/2] + F[n/3] + F[n/4]) function maxValue( N) { // Auxuliary DP array var dp = [] ; // Function call to // build DP array build(dp, N); // Print the answer document.write(dp[N]); } // Driver code // Given N var N = 12; // Function Call maxValue(N); </script> |
Output
13
Time Complexity: O(N)
Space Complexity: O(N)
Dynamic Programming using Top-Down Approach: As in the above approach there are many Overlapping Subproblems for each recursive call. Therefore, to optimize the above approach, the idea is to use the auxiliary space map to store the value calculated in each recursive call and return the recurring stored state. Below are the steps:
- Initialize a map Map to store the value calculated at each recursive call.
- Base Case: If the value of N is 0 or 1 then the result is 0 and 1 respectively. Also, if there is any previously calculated state then return that value as:
>Base Case:
if(N <= 1) {
return N;
}
Memoized State:
if(Map.find(N) != Map.end()) {
return Map[N];
}
- Recursive Call: If the base case is not met, then find the value of the current state by recursively calling for each state as:
result = max(N, recursive_function(N/2) + recursive_function(N/3) + recursive_function(N/4))
- Return Statement: At each recursive call(except the base case), store the current state calculated in the above step in the map and return the value calculated as the result for the current state.
Map[N] = result;
return result;
- After the above steps, print the value return to the end of all the recursive calls.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Map used for memoization map<int, int> mp; // Function to find maximum value // of the given recurrence relation int maxValue(int N) { // Base Case if (N <= 1) return N; // If previously computed if (mp[N] != 0) return mp[N]; // Computing value of function // when its not already computed int ans = max(N, maxValue(N / 2) + maxValue(N / 3) + maxValue(N / 4)); // Storing value for further // computation reduction mp[N] = ans; return ans; } // Utility function to find maximum value // of the given recurrence relation void maxValueUtil(int N) { // Stores final result int result = maxValue(N); // Print the result cout << result; } // Drive Code int main() { // Given N int N = 12; // Function Call maxValueUtil(N); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Map used for memoization static Map<Integer, Integer> mp = new HashMap<>(); // Function to find maximum value // of the given recurrence relation static int maxValue(int N) { // Base Case if (N <= 1) return N; // If previously computed if (mp.containsKey(N)) return mp.get(N); // Computing value of function // when its not already computed int ans = Math.max(N, maxValue(N / 2) + maxValue(N / 3) + maxValue(N / 4)); // Storing value for further // computation reduction mp.put(N, ans); return ans; } // Utility function to find maximum value // of the given recurrence relation static void maxValueUtil(int N) { // Stores final result int result = maxValue(N); // Print the result System.out.print(result); } // Driver code public static void main (String[] args) { // Given N int N = 12; // Function Call maxValueUtil(N); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Map used for memoization mp = {} # Function to find maximum value # of the given recurrence relation def maxValue(N): # Base Case if (N <= 1): return N # If previously computed if (N in mp): return mp[N] # Computing value of function # when its not already computed ans = (max(N, maxValue(N // 2) + maxValue(N // 3) + maxValue(N // 4))) # Storing value for further # computation reduction if(N in mp): mp[N] = ans else: mp[N] = mp.get(N, 0) + ans return ans # Utility function to find maximum value # of the given recurrence relation def maxValueUtil(N): # Stores final result result = maxValue(N) # Print the result print(result) # Drive Code if __name__ == '__main__': # Given N N = 12 # Function Call maxValueUtil(N) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Map used for memoization static Dictionary<int, int> mp = new Dictionary<int, int>(); // Function to find maximum value // of the given recurrence relation static int maxValue(int N) { // Base Case if (N <= 1) return N; // If previously computed if (mp.ContainsKey(N)) return mp[N]; // Computing value of function // when its not already computed int ans = Math.Max(N, maxValue(N / 2) + maxValue(N / 3) + maxValue(N / 4)); // Storing value for further // computation reduction mp.Add(N, ans); return ans; } // Utility function to find // maximum value of the given // recurrence relation static void maxValueUtil(int N) { // Stores readonly result int result = maxValue(N); // Print the result Console.Write(result); } // Driver code public static void Main(String[] args) { // Given N int N = 12; // Function Call maxValueUtil(N); } } // This code is contributed by Princi Singh |
Javascript
<script> // C++ program for the above approach // Map used for memoization let mp= new Map; // Function to find maximum value // of the given recurrence relation function maxValue( N) { // Base Case if (N <= 1) return N; // If previously computed if (mp[N]) return mp[N]; // Computing value of function // when its not already computed let ans = Math.max(N, maxValue(Math.floor(N / 2) ) + maxValue(Math.floor(N / 3)) + maxValue(Math.floor(N / 4))); // Storing value for further // computation reduction mp[N] = ans; return ans; } // Utility function to find maximum value // of the given recurrence relation function maxValueUtil( N) { // Stores final result let result = maxValue(N); // Print the result document.write(result); } // Drive Code // Given N let N = 12; // Function Call maxValueUtil(N); </script> |
Output
13
Time Complexity: O(log N)
Auxiliary Space: O(log N)
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!
