Problem

Submissions

Hints & solutions

Discuss

Break The Integer

Moderate

0/80

Average time to solve is 30m

Contributed by

2 upvotes

Asked in companies

Problem statement

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.

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 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

Sample Input 1:

2
3
4

Sample Output 1:

2
4

Explanation For Sample Input 1:

For the first test case:-

3 can breaked in following ways :-
3 = 1 + 1 + 1. Product = 1 * 1 * 1 = 1
3 = 2 + 1 . Product = 2 * 1 = 1

Out of the above two possible ways the maximum possible product is 2.

For the second case:-

4 = 1 + 1 + 1 + 1 . Product = 1 * 1 * 1 * 1 = 1
4 = 2 + 2 . Product = 2 * 2 = 4
4 = 3 + 1.  Product = 3 * 1 = 3

Out of the above three possible ways the maximum possible product is 4.

Sample Input 2:

2
13
14

Sample Output 2:

108
162

Hint 1

Hint 2

Break the given integer ‘N’ into all possible ways.

Approaches (3)

Approach 1

Approach 2

Approach 3

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.

Time Complexity

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!.

Space Complexity

O(1)

We are using constant space to solve this.

(100% EXP penalty)

Break The Integer

Console