Teaching Kids Programming: Videos on Data Structures and Algorithms
Given N squares which side is M, we want to re-arrange it to form a larger rectangle. We want to maximize the Perimeter.
Algorithm to Compute Maximal Perimeter by Forming a Rectangle from N squares
For N=6 squares M=3, we have the following two solutions: 3×2 or 1×6. We have other variants but they are the same (not affecting the permiter because it can be simply rotated or flipped from existing variant).
If we place it like 3×2 (or 2×3) – like this:
AAA
AAA
The permiter is 72-14*3=30
If we place it horizontally one by one – like this:
AAAAAA
The permiter is 72-10*3=42
So, the greedy strategy is to avoid more internal joint edges by putting them one by one next to each other along the same row:
The answer is which is
Translated into Python code:
1 2 | def maxPerimeter(n, m): return (2*n+2)*m |
def maxPerimeter(n, m): return (2*n+2)*m
The time and space complexity is O(1) constant.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Compute the Max Fence Area via Bruteforce Algorithm or Parabola Quadratic Equation
Next Post: Teaching Kids Programming - Finding Real Roots of a Quadratic Equation