Maximum Sum Problem

Posted: 25 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a number N that can be broken into three parts N / 2, N / 3, and N / 4 (considering only integer parts). Each number obtained in this process can be divided further recursively. Your task is to find the maximum sum that can be obtained by summing up the divided parts together.

Note:
The maximum sum may be obtained without dividing N also.
For example :
N = 12 breaking N into three parts will give 6, 4, and 3 which gives us the sum = 13. Further breaking 6, 4, and 3 into other parts will give us a sum less than or equal to 6, 4, and 3 respectively. Therefore, the maximum answer will be 13.
Input format :
The first line of input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains a single integer N.
Output format :
 For each test case, in a separate line, print a single integer which is the maximum sum. 
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 3000

Time Limit : 1 sec
Approach 1

The idea is to use recursion in each call. In each call we have two options: either break the number or not. Thus, to explore all the possibilities we will use recursion.

 

  • Check for the base condition if the number is 1 or 0 return it.
  • Else, recursively call the function for N/2, N/3, and N/4.
  • Calculate the sum of these numbers obtained from the above step.
  • Return the maximum of N and the sum obtained in the above step.
Try Problem