Problem

Submissions

Hints & solutions

Discuss

Maximum Sum Problem

Easy

0/40

Average time to solve is 15m

Contributed by

1 upvote

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
19
21

Sample Output 1 :

19
22

Explanation For Sample Input 1:

For the first test case:
Given N = 19, breaking it into three parts {9, 6, 4} which gives a sum of 19, and further breaking these three numbers will still produce less than or equal sum to 19. Therefore, the answer will be 19.

For the second test case:
Given N = 21, breaking it into three parts {10, 7, 5} which gives a sum of 22, and further breaking these three numbers will still produce less than or equal sum to 22. Therefore, the answer will be 22.

Sample Input 2 :

Sample Output 2 :

4
30
13

Hint 1

Hint 2

Hint 3

Can you do it recursively?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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.

Time Complexity

O(log(N)), where N denotes the given number.

Since we are making three calls and every time number is getting divided either by 2 or 3 or 4 therefore total maximum calls will be log2(N).

Space Complexity

O(N),

We are using recursion stack space of max size N/2. Thus, space complexity will be O(N).

(100% EXP penalty)

Maximum Sum Problem

Console