minimum-cuts-to-divide-a-circle

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A valid cut in a circle can be:

<ul>
	<li>A cut that is represented by a straight line that touches two points on the edge of the circle and passes through its center, or</li>
	<li>A cut that is represented by a straight line that touches one point on the edge of the circle and its center.</li>
</ul>

Some valid and invalid cuts are shown in the figures below.
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/29/alldrawio.png" style="width: 450px; height: 174px;" />
Given the integer <code>n</code>, return the minimum number of cuts needed to divide a circle into <code>n</code> equal slices.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/24/11drawio.png" style="width: 200px; height: 200px;" />
<pre>
Input: n = 4
Output: 2
Explanation: 
The above figure shows how cutting the circle twice through the middle divides it into 4 equal slices.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/24/22drawio.png" style="width: 200px; height: 201px;" />
<pre>
Input: n = 3
Output: 3
Explanation:
At least 3 cuts are needed to divide the circle into 3 equal slices. 
It can be shown that less than 3 cuts cannot result in 3 slices of equal size and shape.
Also note that the first cut will not divide the circle into distinct parts.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>

numberOfCuts

Minimum Cuts to Divide a Circle

Smallest Even Multiple

smallest-even-multiple

最小偶倍数

Count Total Number of Colored Cells

count-total-number-of-colored-cells

统计染色格子数

Geometry

Math

圆内一个 有效切割&nbsp;，符合以下二者之一：

<ul>
	<li>该切割是两个端点在圆上的线段，且该线段经过圆心。</li>
	<li>该切割是一端在圆心另一端在圆上的线段。</li>
</ul>

一些有效和无效的切割如下图所示。

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/29/alldrawio.png" style="width: 450px; height: 174px;" />

给你一个整数&nbsp;<code>n</code>&nbsp;，请你返回将圆切割成相等的&nbsp;<code>n</code>&nbsp;等分的&nbsp;最少&nbsp;切割次数。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/24/11drawio.png" style="width: 200px; height: 200px;" />

<pre>
输入：n = 4
输出：2
解释：
上图展示了切割圆 2 次，得到四等分。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/24/22drawio.png" style="width: 200px; height: 201px;" />

<pre>
输入：n = 3
输出：3
解释：
最少需要切割 3 次，将圆切成三等分。
少于 3 次切割无法将圆切成大小相等面积相同的 3 等分。
同时可以观察到，第一次切割无法将圆切割开。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>