Pythonで配列を右回転して1～nの連続数列（昇順・降順）にできるか判定するプログラム

問題の概要

n 個の要素を含む数値リスト nums が与えられたとします。nums を任意の回数だけ右に回転（シフト）することで、[1, 2, ..., n]（昇順）または [n, n-1, ..., 1]（降順）という「最初の n 個の自然数」の並びにできるかどうかを判定します。

たとえば、入力が nums = [5, 6, 1, 2, 3, 4] の場合、4 回右に回転すると [1, 2, 3, 4, 5, 6] になるため、答えは True となります。

解法の考え方

鍵となるのは「隣接する要素の差」に注目することです。1 から n までの数字を環状につなげると、隣り合う数字同士の差は 1 になり、環のつなぎ目（1 と n）の差は n-1 になります。したがって、回転によって昇順・降順の数列にできるためには、配列内のすべての隣接要素の差の絶対値が 1 または n-1 でなければなりません。

逆に、この条件がすべて満たされていれば、その並びは「1～n の環状の順序に沿った一筆書きの経路」となり、適切な位置で切る（＝回転する）ことで必ず昇順か降順の数列にできます。

アルゴリズムの手順

• n を nums のサイズとします。
• i を 1 から n-1 まで順に調べます。
  • |nums[i-1] - nums[i]| が 1 でも n-1 でもない場合は、False を返します。
• すべての隣接ペアが条件を満たしていれば、True を返します。

Pythonでの実装例

def solve(nums):
    n = len(nums)
    for i in range(1, n):
        if abs(nums[i - 1] - nums[i]) != 1 and abs(nums[i - 1] - nums[i]) != n - 1:
            return False
    return True

nums = [5, 6, 1, 2, 3, 4]
print(solve(nums))

入力

[5, 6, 1, 2, 3, 4]

出力

True

補足：より堅牢にするには

このアルゴリズムは、nums が 1 から n までの数字をそれぞれ 1 回ずつ含んでいることを前提としています。重複や範囲外の値が混入する可能性がある場合は、次のようなチェックを最初に追加しておくと安全です。

if set(nums) != set(range(1, n + 1)):
    return False

計算量

配列を一度走査するだけなので、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。大きな配列でも効率的に判定できるのが特徴です。