Max Volume Of Cube

Difficulty: Easy

Jimmy puts Ann's birthday present in a cuboid box. The dimensions of its edges are positive integers and the sum of its length, width, and height is N.

What is the maximum volume Ann's present box can have?

                                                length+width+height=N$$

Input Format

A single integer, N (the sum of the box's length, width, and height).

Constraint
3≤N≤103

Output Format

Print the maximum possible volume of the box. 

Sample Input 0

4

Sample Output 0

2

Sample Input 1

8

Sample Output 1

18

Explanation

Sample 0
Here, our only possible dimensions are some combination of 1, 1, and 2. Volume=1×1×2=2.

Sample 1 
Here are all possible edge dimensions:
[1,1,6], Volume=6.
[1,2,5], Volume=10.
[1,3,4], Volume=12.
[2,2,4], Volume=16.
[2,3,3], Volume=18.

We print the maximum volume, which is 18.

Runtime Analysis:

Given the only constraint that N is between 3 and 103, we know that pretty much most algorithms besides a pure brute force can solve this problem. An entirely brute force approach O(n3), involving going over every possible length, width, height from 1 to N and saving the l * w * h when l + w + h = n will fail as 109 would cause a time out. This problem can be solved O(n2) or O(1).

Runtime: O(n2) or O(1)

Algorithmic Approach:

O(n2): This question involves some basic mathematical reasoning. There is really no need to loop for all possibly length, widths, heights. If you simply loop:

1. length from 1 to N
2. width from 1 to N - length

You can infer the height from (N - length - width). You would just have to keep track of the max value for:

 Length * width * (N - length - width)

Thus, making an O(n2) solution. 

Java Code: O(n2)

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
   
        int ans = 0;
        
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n && i+j<=n;j++)
                ans = Math.max(ans, i*j*(n-i-j));
        
        System.out.println(ans);
        
       
    }
}

O(1): If you think a bit further and walk through a couple examples of this problem with smaller numbers, you will notice that the largest volumes are always made when the length, width, and height values are as close to each other as possible. In the case that N is divisible by 3, your length, width, and height would all be equal to N/3. 

In order to divide the sides as equally as possible:

Length = N/3
Width = (N - N/3) / 2
Height = (N - Length - Width)

Java Code: O(1)

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        int a = n/3;
        int b = (n - n/3) / 2;
        int c = n - (a + b);
        
        System.out.println(a * b * c);
        
    }
}