We are given the sum of length, breadth and height, say S, of a cuboid. The task is to find the maximum volume that can be achieved so that sum of side is S.
Volume of a cuboid = length * breadth * height
Examples :
Input : s = 4
Output : 2
Only possible dimensions are some combination of 1, 1, 2.
Input : s = 8
Output : 18
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
Method 1: (Brute Force)
The idea to run three nested, one for length, one for breadth and one for height. For each iteration, calculate the volume and compare with maximum volume.
Below is the implementation of this approach:
C++
#include <bits/stdc++.h>
using namespace std;
int maxvolume(int s)
{
int maxvalue = 0;
for (int i = 1; i <= s - 2; i++) {
for (int j = 1; j <= s - 1; j++) {
int k = s - i - j;
maxvalue = max(maxvalue, i * j * k);
}
}
return maxvalue;
}
int main()
{
int s = 8;
cout << maxvolume(s) << endl;
return 0;
}
|
Java
class GFG
{
static int maxvolume(int s)
{
int maxvalue = 0;
for (int i = 1; i <= s - 2; i++)
{
for (int j = 1; j <= s - 1; j++)
{
int k = s - i - j;
maxvalue = Math.max(maxvalue, i * j * k);
}
}
return maxvalue;
}
public static void main (String[] args)
{
int s = 8;
System.out.println(maxvolume(s));
}
}
|
Python3
def maxvolume (s):
maxvalue = 0
i = 1
for i in range(s - 1):
j = 1
for j in range(s):
k = s - i - j
maxvalue = max(maxvalue, i * j * k)
return maxvalue
s = 8
print(maxvolume(s))
|
C#
using System;
class GFG
{
static int maxvolume(int s)
{
int maxvalue = 0;
for (int i = 1; i <= s - 2; i++)
{
for (int j = 1; j <= s - 1; j++)
{
int k = s - i - j;
maxvalue = Math.Max(maxvalue, i * j * k);
}
}
return maxvalue;
}
public static void Main ()
{
int s = 8;
Console.WriteLine(maxvolume(s));
}
}
|
PHP
<?php
function maxvolume( $s)
{
$maxvalue = 0;
for ( $i = 1; $i <= $s - 2; $i++)
{
for ( $j = 1; $j <= $s - 1; $j++)
{
$k = $s - $i - $j;
$maxvalue = max($maxvalue,
$i * $j * $k);
}
}
return $maxvalue;
}
$s = 8;
echo(maxvolume($s));
?>
|
Javascript
<script>
function maxvolume( s)
{
let maxvalue = 0;
for (let i = 1; i <= s - 2; i++)
{
for (let j = 1; j <= s - 1; j++)
{
let k = s - i - j;
maxvalue = Math.max(maxvalue, i * j * k);
}
}
return maxvalue;
}
let s = 8;
document.write(maxvolume(s));
</script>
|
Output :
18
Time Complexity: O(n2)
Auxiliary Space: O(1)
Method 2: (Efficient approach)
The idea is to divide edges as equally as possible.
So,
length = floor(s/3)
width = floor((s – length)/2) = floor((s – floor(s/3)/2)
height = s – length – width = s – floor(s/3) – floor((s – floor(s/3))/2)
Below is the implementation of this approach:
C++
#include <bits/stdc++.h>
using namespace std;
int maxvolume(int s)
{
int length = s / 3;
s -= length;
int breadth = s / 2;
int height = s - breadth;
return length * breadth * height;
}
int main()
{
int s = 8;
cout << maxvolume(s) << endl;
return 0;
}
|
Java
import java.io.*;
class GFG
{
static int maxvolume(int s)
{
int length = s / 3;
s -= length;
int breadth = s / 2;
int height = s - breadth;
return length * breadth * height;
}
public static void main (String[] args)
{
int s = 8;
System.out.println ( maxvolume(s));
}
}
|
Python3
def maxvolume( s ):
length = int(s / 3)
s -= length
breadth = s / 2
height = s - breadth
return int(length * breadth * height)
s = 8
print( maxvolume(s) )
|
C#
using System;
class GFG
{
static int maxvolume(int s)
{
int length = s / 3;
s -= length;
int breadth = s / 2;
int height = s - breadth;
return length * breadth * height;
}
public static void Main ()
{
int s = 8;
Console.WriteLine( maxvolume(s));
}
}
|
PHP
<?php
function maxvolume($s)
{
$length = (int)($s / 3);
$s -= $length;
$breadth = (int)($s / 2);
$height = $s - $breadth;
return $length * $breadth * $height;
}
$s = 8;
echo(maxvolume($s));
?>
|
Javascript
<script>
function maxvolume( s)
{
let length = parseInt(s / 3);
s -= length;
let breadth = parseInt(s / 2);
let height = s - breadth;
return length * breadth * height;
}
let s = 8;
document.write(maxvolume(s));
</script>
|
Output :
18
Time Complexity: O(1)
Auxiliary Space: O(1)
How does this work?
We basically need to maximize product of
three numbers, x, y and z whose sum is given.
Given s = x + y + z
Maximize P = x * y * z
= x * y * (s – x – y)
= x*y*s – x*x*s – x*y*y
We get dp/dx = sy – 2xy – y*y
and dp/dy = sx – 2xy – x*x
We get dp/dx = 0 and dp/dy = 0 when
x = s/3, y = s/3
So z = s – x – y = s/3
Please suggest if someone has a better solution which is more efficient in terms of space and time.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
