Maximum Sum Problem Statement

Given an integer N, your task is to recursively break it into three integer parts: N / 2, N / 3, and N / 4. You need to compute the maximum sum possible by dividing the number further. Note that the maximum sum may also be achieved without dividing N.

Input:

The first line contains an integer T, representing the number of test cases.
Each of the following lines contains a single integer N.

Output:

For each test case, output in a separate line the maximum obtainable sum.

Example:

Input:
2
12
2
Output:
13
2
Explanation:

For N = 12, breaking it into 6, 4, and 3 gives a sum of 13, which is greater than any further possible division.
For N = 2, dividing results in 0, 0, and 0. The maximum sum is therefore N itself, which is 2.

Constraints:

  • 1 <= T <= 5
  • 1 <= N <= 3000

Note: There is no need to print anything within the function; just return the calculated result for each test case.

AnswerBot
8d

Given an integer N, recursively break it into three parts and find the maximum sum possible.

  • Recursively divide N into N/2, N/3, and N/4 to find the maximum sum

  • Compare the sum obtained by dividing N wi...read more

Help your peers!
Add answer anonymously...
Morgan Stanley Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter