Break The Integer
Ninja is given an integer ‘N’ . One day Ninja decides to break the integer into K positive parts (K=2) such that the sum of all parts is equal to ‘N’.Ninja wants to maximize the product of all the ‘K’ parts.

Help Ninja in helping what maximum possible product it can obtain by breaking the integer ‘N’ into ‘K’ positive parts where ‘K’ can be any integer greater than 2.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first and only line of the test case consists of a single integer ‘N’.

Output Format:

Return the maximum possible product Ninja can obtain by breaking integer ‘N’ into ‘K’ parts.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Break The Integer

Ninja is given an integer ‘N’ . One day Ninja decides to break the integer into K positive parts (K>=2) such that the sum of all parts is equal to ‘N’.Ninja wants to maximize the product of all the ‘K’ parts.

Help Ninja in helping what maximum possible product it can obtain by breaking the integer ‘N’ into ‘K’ positive parts where ‘K’ can be any integer greater than 2.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first and only line of the test case consists of a single integer ‘N’.

Output Format:

Return the maximum possible product Ninja can obtain by breaking integer ‘N’ into ‘K’ parts.

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 11
2 <= ‘N’ <= 55

Time Limit: 1 sec

Accepted Answer

The approach would be to think the max product that we could get on breaking a number N into two factors. This product can be represented by the following function : f = x(N-x).
The maximum of this function is achieved when x = N/2.
However, factors should be integers. Thus the maximum is (N/2)*(N/2) when N is even or (N-1)/2 *(N+1)/2 when N is odd.
When the maximum of f is larger than N, we should do the break.
(N/2)*(N/2)>=N, then N>=4
(N-1)/2 *(N+1)/2>=N, then N>=5
These two expressions mean that factors should be less than 4, otherwise we can do the break and get a better product. The factors in last result should be 1, 2 or 3. Obviously, 1 should be abandoned. Thus, the factors of the perfect product should be 2 or 3.
Next thing is 6 = 3 + 3 = 2 + 2 + 2, but 3 * 3 > 2 * 2 * 2, that is every triplet of 2 can be replaced with tuple of 3 for maximum product, so we will keep breaking the number in terms of 3 only, until number remains as 4 or 2, which we will be broken into 2*2 (2*2 > 3*1) and 2 respectively and we will get our maximum product.

Accepted Answer

Brute Force

The main idea is to break the given integer ‘N’ into all possible ways and out of all possible ways the one with the maximum product will be the answer.

Algorithm:

Create a recursive function calculate(int N,int ch=0).
The base case for the function should be if N==0 || N==1 return 1.
Run a loop from i equal to 1 to N+(ch==1).
The recursive call for the above function will be:-

In the end, return ans.

Space Complexity: O(1)Explanation:

O(1)

We are using constant space to solve this.

Time Complexity: O(n!)Explanation:

O(N!) where ‘N’ is the given number.

For each recursive call, we are calling the recursion maximum N times. Hence time complexity will be N!.

Accepted Answer

Memoisation Approach

In Approach 1 there are many overlapping sub-cases Hence we will apply memoization in Approach 1 to avoid calculating sub-problems many times.

In the above sub-tree, we are calculating 2 two times and 1 two times.So we will use memoization to avoid calculating same problems.

Algorithm:

Create an auxiliary dp array of size N+1.
Create a recursive function calculate(int N,int dp[],int ch=0).
The base case for the function should be if N==0 || N==1 return 1.
Add memoization condition if dp[N]!=-1 return dp[N].
The recursive call will be:-

In the end return dp[N]=ans.

Space Complexity: O(n)Explanation:

O(N) where ‘N’ is the given number.

We are creating an auxiliary 1D array ‘dp’ of size N for memoization.

Time Complexity: O(n)Explanation:

O(N) where ‘N’ is the given number.

We are calculating the answer for 0 to N.Hence time complexity will be O(N).

C++ (g++ 5.4)

/*

    Time Complexity:O(N)

    Space Complexity:O(N)

    

    where N is given number.

*/



int find(int N, vector &dp, int ch = 0)

{

	// Base case for recursion.

	if (N == 0 || N == 1)

	{

		return 1;

	}



	// Memoization Condition.

	if (dp[N] != -1)

	{

		return dp[N];

	}



	int ans = 1;



	// Considering all possible cases.

	// When ch==1 it means we can include N also in possible ways.

	// Initially N cannot be included as K will be 1 in that case.

	for (int i = 1; i < N + (ch == 1); i++)

	{

		int ctr = find(N - i, dp, 1);

		ans = max(ans, i * ctr);

	}

	return  dp[N] = ans;





}



int breakTheInteger(int N)

{

	vectordp(N + 1, -1);



	return find(N, dp);

}

Python (3.5)

"""

    Time Complexity:O(N)

    Space Complexity:O(N)

    

    where N is given number.

"""



def find(N, dp,ch = 0):



	# Base case for recursion.

	if (N == 0 or N == 1):

	

		return 1

	

	# Memoization Condition.

	if (dp[N] != -1):

	

		return dp[N]

	

	ans = 1

	

    # Considering all possible cases.

	# When ch==1 it means we can include N also in possible ways.

	# Initially N cannot be included as K will be 1 in that case.

	for i in range(1,N+(1 if ch==1 else 0)):

	

		ctr = find(N - i, dp, 1)

		ans = max(ans, i * ctr)

		

	dp[N] = ans



	return ans



def breakTheInteger(N):



	dp=[-1]*(N+1)



	return find(N, dp)

Java (SE 1.8)

/*

    Time Complexity:O(N)

    Space Complexity:O(N)

    

    where N is given number.

*/



public class Solution 

{

	public static int[] dp;



	public static int find(int N, int ch) 

	{

		// Base case for recursion.

		if (N == 0 || N == 1) 

		{

			return 1;

		}



		// Memoization Condition.

		if (dp[N] != -1) 

		{

			return dp[N];

		}



		int ans = 1;



		// Considering all possible cases.

		// When ch==1 it means we can include N also in possible ways.

		// Initially N cannot be included as K will be 1 in that case.

		for (int i = 1; i < N + (ch == 1 ? 1 : 0); i++) 

		{

			int ctr = find(N - i, 1);

			ans = Math.max(ans, i * ctr);

		}



		return  dp[N] = ans;

	}

	public static int breakTheInteger(int N) 

	{

		dp = new int[N + 1];



		for (int i = 0; i <= N; i++) 

		{

			dp[i] = -1;

		}



		return find(N, 0);

	}

}

Top Info Edge Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Info Edge Software Engineer