A city planner wants to repave a circular plaza into n equal wedge-shaped sections using the fewest possible straight boundary lines. Each boundary line is drawn straight across the plaza from one edge of the circle to another (it may or may not pass through the exact center), and any number of these lines may be drawn before the sections are measured. Given the desired number of equal sections n, determine the minimum number of straight lines required so that the plaza ends up divided into exactly n sections of equal area.
A single integer n on one line.
A single integer: the minimum number of straight lines needed.
Example 1
Input
4
Expected
2
Explanation
Four equal sections can be produced by drawing 2 lines through the center (each such diameter line creates two opposite equal sections simultaneously), so the minimum is 4 / 2 = 2.
Example 2
Input
3
Expected
3
Explanation
Three equal sections is an odd count greater than 1, so no line through the center can be used (a diameter always produces an even number of opposite sections). Instead 3 separate chords, each avoiding the center, must be drawn to carve out the three equal wedges, so the minimum is 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →