Herb and Bjarne · Coding Gym

See the original problem on HackerRank.

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

Input Format

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

Constraints

\(3 \leq N \leq 10^3\)

Output Format

Print the maximum possible volume of the box.

Solutions

The product of edge lengths is maximized when the lenghts are as long as possible.That is, we have to evenly distribute the available lenght through the edges and then give the possible remainder two one or two edges (the remainder is at most 2 because we divde by 3).

We start by setting all edges to \(N/3\) and then we just distribute the remainder evenly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int n;
cin >> n;
array<int, 3> nums;
nums.fill(n / 3);
auto remainder = n%3;
auto volume = 1;
for (auto i=0; i<3; ++i)
{
    volume *= nums[i] + (remainder-- > 0);
}
cout << volume;

The same can be implemented with reduce pattern:

1
2
3
4
5
6
7
8


int n;
cin >> n;
array<int, 3> nums;
nums.fill(n / 3);
auto remainder = n%3;
cout << std::accumulate(begin(nums), end(nums), 1, [&](int curr, int nxt){
	return curr * (nxt + (remainder-- > 0));
}) << endl;

In Rust we can explain it with enumerate, map, product:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


fn solve(n: usize) -> usize {
    const DIM: usize = 3;
    let x = n / DIM;
    let r = n % DIM;
    std::iter::repeat(x)
        .take(DIM)
        .enumerate()
        .map(|(i, x)| x + ((i < r) as usize))
        .product()
}

The solution above is generalized on DIM, the number of dimension. It is a box, so the dimension is 3. Due to this fact, we can write it with primitive types and operations:

1
2
3
4
5
6
7


fn solve(n: usize) -> usize {
    let x = n / 3;
    let r = n % 3;
    (x + ((0 < r) as usize)) *
    (x + ((1 < r) as usize)) *
    (x + ((2 < r) as usize))
}

Note that Rust compiler produces exactly the same machine code for the two programs above. Here an x86_64 assembly code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


example::solve:
        movabs  rcx, -6148914691236517205
        mov     rax, rdi
        mul     rcx
        shr     rdx
        lea     rax, [rdx + 2*rdx]
        sub     rdi, rax
        cmp     rdi, 1
        mov     rcx, rdx
        sbb     rcx, -1
        xor     eax, eax
        cmp     rdi, 1
        seta    al
        add     rax, rdx
        imul    rcx, rdx
        imul    rax, rcx
        ret

math