Q:

Given a number n, we can divide it into only three parts n/2, n/3 and n/4 (we will consider only integer part). The task is to find the maximum sum we can make by dividing the number into three parts recursively and summing up them together

mahmoud2506
Save to bookmark
|
2022-04-30
|
  244 
0

Maximum Sum Problem

Given a number n, we can divide it into only three parts n/2, n/3 and n/4 (we will consider only integer part). The task is to find the maximum sum we can make by dividing the number into three parts recursively and summing up them together.

Note: Sometimes, the maximum sum can be obtained by not dividing n.

    Input:
    The first line of input contains an integer T denoting the number of test cases. 
    Then T test cases follow. The first line of each test case contains the integer n.
    
    Output:
    For each test case, in a new line, print the maximum sum possible.

Example:

    Input:
    2
    12 
    24

    Output:
    13 
    27

Explanation:

    Say for the first example,
    N=12

    N can be divided in n/2(6), n/3(4) & n/4(3). 
    6 can be divided as 3, 2, 1. 
    3 can be divided as 1, 1, 0
    So if n=3 then max sum possible is 3 itself

    2 can be divided as 1, 0, 0
    So if n=2 then max sum possible is 2 itself
    1 can't be divided so, if n=1 then max sum possible is 1 itself

    So, for n=6 max sum possible is either 6 or 3+2+1 whichever maximum, and its 6

    Similarly for n=4 max sum possible is 4 (do it yourself)
    For n=3, max sum possible is 3 (already found while computing for 6)

    So for n=12
    Max sum possible is either 12 or (max sum (6) + max sum (4) + max sum (3) = 13), 
    so it's 13
    Check the following tree for proper understanding.
    

    Maximum sum problem
    

    Try the second example of n=24 yourself.
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

Obviously, this is recursion. The recursive algorithm can be,

    Function axsum:
        1) Base case: if n is 0 or n is 1 return n;
        2) Return maximum( n,maxsum(n/2) + maxsum(n/3)+maxsum(n/4))

This is the same as what I did in the above explanation. Compute until you reach the base case. But, the recursive solution will generate many overlapping subproblems which will be computed again and again. Check the above recursion tree for n=12, and you can find there have been multiple instances of subproblem 3 & 2 which are to be computed multiple times. If such small input generates these many overlapping subproblems then for large input it will be computationally very expensive. So, to overcome this overhead, we use dynamic programming which is storing the computed subproblems and use it whenever required again without further computing. This will reduce the overhead.

To store the computations we use dp an array with dimension equal to input size n

So,

    1)  Initialize dp[n+1] with the index value. 
        That is, dp[0]=0,dp[1]=1 ,dp[2] =2 and so on. 
        This covers to thing.
            i)  It covers base case that is for n=0 or 1
            ii) It initializes each sub problem of size i with value i 
                which is the least value of the maximum sum. 
                If maximum sum can't be availed by dividing then 
                it will return i,sub problem size 
    2)  for i=2 to n
            dp[i]=maximum(dp[i],dp[i/2]+dp[i/3]+dp[i/4])   
    3)  Return dp[n]

This has time complexity of O(n) and space complexity of O(n).

N.B: To bring more optimization on multiple test cases, create a global array and pre-compute it. The global array should be based on input constraints. Check the following implementation.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

void print(vector < int > a, int n) {
  for (int i = 0; i < n; i++)
    cout << a[i] << " ";
  cout << endl;
}

// global dp array, size as per constraint, here n<=100000
int arr[100001];

// recursive solution
int findmax(int n) {
  if (n <= 1)
    return n;

  int p = findmax(n / 2) + findmax(n / 3) + findmax(n / 4);

  return n > p ? n : p;
}

int main() {
  int t, n, item;

  // precompute the dp array
  arr[0] = 0;
  arr[1] = 1;

  for (int i = 2; i <= 100000; i++) {
    int p = arr[i / 4] + arr[i / 3] + arr[i / 2];
    arr[i] = i > p ? i : p;
  }

  cout << "Number of testcase:\n";
  scanf("%d", & t);

  for (int i = 0; i < t; i++) {

    cout << "Enter n\n";
    scanf("%d", & n);

    cout << "Maximum sum is: " << arr[n] << endl;
    // cout<<findmax(n)<<endl; 
    // if you want to check recursive one and have 
    // a long day to check for large n
  }

  return 0;
}

Output

 

Number of testcase:
2
Enter n
12
Maximum sum is: 13
Enter n
24
Maximum sum is: 27

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given an array you have to print the longest biton... >>
<< Given two strings S and T, find the number of time...