Widest Common Tile
EasyMath & GeometryFree
Problem
A carpenter has planks of the given integer lengths. She wants to cut every plank into pieces of one single length, with nothing left over on any plank.
Return the largest piece length that works for all planks at once.
Example 1
- Input:
- lengths = [12, 18, 30]
- Output:
- 6
6 divides 12, 18 and 30, and no larger length divides all three.
Example 2
- Input:
- lengths = [8, 9]
- Output:
- 1
Example 3
- Input:
- lengths = [7]
- Output:
- 7
A single plank can stay whole.
Constraints
- 1 ≤ lengths.length ≤ 10^5
- 1 ≤ lengths[i] ≤ 10^9
Hint
Show the first hint
The answer is the greatest common divisor of all the lengths.
Walkthrough
How to approach it
01Clarify before coding
- Are lengths positive? Yes, all at least 1, so the gcd is well defined and at least 1.
- Can there be a single plank? Yes: the answer is its own length.
- Can I use a library gcd? Say you can, but be ready to write Euclid yourself, which is what is being tested.
02Brute force
Try every candidate from min(lengths) down to 1 and return the first that divides every length.
Cost: O(min · n): with a minimum of 10^9 and 10^5 planks that is up to 10^14 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.