minimum-number-of-operations-to-reinitialize-a-permutation

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an even integer <code>n</code>​​​​​​. You initially have a permutation <code>perm</code> of size <code>n</code>​​ where <code>perm[i] == i</code>​ (0-indexed)​​​​.

In one operation, you will create a new array <code>arr</code>, and for each <code>i</code>:

<ul>
	<li>If <code>i % 2 == 0</code>, then <code>arr[i] = perm[i / 2]</code>.</li>
	<li>If <code>i % 2 == 1</code>, then <code>arr[i] = perm[n / 2 + (i - 1) / 2]</code>.</li>
</ul>

You will then assign <code>arr</code>​​​​ to <code>perm</code>.

Return the minimum non-zero number of operations you need to perform on <code>perm</code> to return the permutation to its initial value.

&nbsp;
Example 1:

<pre>
Input: n = 2
Output: 1
Explanation: perm = [0,1] initially.
After the 1st operation, perm = [0,1]
So it takes only 1 operation.
</pre>

Example 2:

<pre>
Input: n = 4
Output: 2
Explanation: perm = [0,1,2,3] initially.
After the 1st operation, perm = [0,2,1,3]
After the 2nd operation, perm = [0,1,2,3]
So it takes only 2 operations.
</pre>

Example 3:

<pre>
Input: n = 6
Output: 4
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>n</code>​​​​​​ is even.</li>
</ul>

reinitializePermutation

Minimum Number of Operations to Reinitialize a Permutation

Array

Math

Simulation

给你一个偶数 <code>n</code>​​​​​​ ，已知存在一个长度为 <code>n</code> 的排列 <code>perm</code> ，其中 <code>perm[i] == i</code>​（下标 从 0 开始 计数）。

一步操作中，你将创建一个新数组 <code>arr</code> ，对于每个 <code>i</code> ：

<ul>
	<li>如果 <code>i % 2 == 0</code> ，那么 <code>arr[i] = perm[i / 2]</code></li>
	<li>如果 <code>i % 2 == 1</code> ，那么 <code>arr[i] = perm[n / 2 + (i - 1) / 2]</code></li>
</ul>

然后将 <code>arr</code>​​ 赋值​​给 <code>perm</code> 。

要想使 <code>perm</code> 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。

 

示例 1：

<pre>
输入：n = 2
输出：1
解释：最初，perm = [0,1]
第 1 步操作后，perm = [0,1]
所以，仅需执行 1 步操作</pre>

示例 2：

<pre>
输入：n = 4
输出：2
解释：最初，perm = [0,1,2,3]
第 1 步操作后，perm = [0,2,1,3]
第 2 步操作后，perm = [0,1,2,3]
所以，仅需执行 2 步操作</pre>

示例 3：

<pre>
输入：n = 6
输出：4
</pre>

 

提示：

<ul>
	<li><code>2 <= n <= 1000</code></li>
	<li><code>n</code>​​​​​​ 是一个偶数</li>
</ul>