Break a number in 3 parts (n/2, n/3, n/4) recursively to get maximum sum

Reading time: 20 minutes | Coding time: 5 minutes

This question is a simple yet confusing problem, and can be asked during a programming interview.

Given a number n, we can divide it in only three parts n/2, n/3 and n/4 recursively (considering only integer part). We have to find the maximum sum that can be made by summing those three parts (n/2 + n/3 + n/4) together.

We will solve this problem in 2 ways:

• Recursive approach O(3^N)
• Dynamic Programming O(N)

For example:

Given n = 16, output is 17, 
as we divide it in three parts, we get
{16/2, 16/3, 16/4} = {8, 5, 4} 
Its sum is = 8 + 5 + 4 = 17, 

now again we break them further,
{8/2, 8/3, 8/4} = {4, 2, 2}, its sum is 8 
and further breaking them will end in getting 1 as maximum sum, 

thus 8 can give maximum sum as 8 only

Similarly for 5 and 4 also we will be getting 5 and 4 respectively as maximum sum, thus the maximum sum we can get by breaking 16 is 8 + 5 + 4 = 17.

Approach 1 : Recursion

A simple and easy method to solve this problem can be breaking the number recursively and checking to get the maximum sum. We can find, max((break(n/2) + break(n/3) + break(n/4)), n) and return it, break(n) is the function used recursively. It will work, as either the sum of the parts would be maximum or the number itself would be maximum.

Pseudocode

1) Check the number for base condition of 0 and 1.
2) Call the function recursively for all three parts.
3) Return the maximum of sum or the number itself.

Recursive Implementation

# Function to find the maximum sum 
def break(n) :
    # number should be atleast greater than 2 for recursive calls
    if (n == 0 or n == 1) :
        return n 
        
    # recursively breaking the number and getting maximum as result
    return max((break(n // 2) + break(n // 3) + break(n // 4)), n) 

# Calling the funtion 
n = 16
print(break(n))

Approach 2 : Dynamic Programming

The recursive approach was very simple, but in terms of efficiency it was not best as while breaking the function recursively we were doing some of the operations multiple times. For example : while calculating result for 16, we called the funtion twice for n=4 (one for 16//4 part and another for 8//2 part), we can avoid this problem by using Dynamic Programming. We can store the result obtained for a number in an array and can invoke that result whenever we find that number again.

Pseudocode

1) Initialise the array for size (n+1).
2) Fill the value of base cases inside array
3) Iterate through n and find result for each, retrieving values required from the array
4) Return thr value at position n inside array.

Dynamic programming Implementation

# Function to find the maximum sum 
def break(n): 
    # Initialing an array
    stored = [0]*(n+1)
    
    # base conditions covered
    stored[0] = 0
    stored[1] = 1
    
    # Using bottom-up method to fill array
    for i in range(2, n+1):
        stored[i] = max(stored[int(i//2)] + stored[int(i/3)] + stored[int(i/4)], i);
    
    return dp[n]

# Calling the funtion 
n = 16
print(break(n)) 

Complexity

The time and space complexity of Dynamic Programming approach are:

• Time Complexity : O(n)
• Space Complexity : O(n) in case of Dynamic programming
• where n is given integer

The time and space complexity of recursive approach are:

• Time Complexity : O(2^n)
• Space Complexity : O(1) in case of Dynamic programming
• where n is given integer