C++で整数Nの回転のうち奇数・偶数になるものをカウントする方法

問題の概要

整数Nが与えられます。この記事のゴールは、Nを回転（ローテート）させたときに奇数になる回転の個数と偶数になる回転の個数を、それぞれ数えることです。

例えば、Nが123の場合、その回転は「123」「321」「132」の3通りになります。このうち奇数になるのは123と321の2個、偶数になるのは132の1個です。

具体的な入出力例で確認してみましょう。

入力例1

入力： N = 54762

出力：

• 奇数になる回転の個数：2
• 偶数になる回転の個数：3

解説： 回転によって生成される数は以下の5つです。

54762、25476、62547、76254、47625

• 偶数になる回転（3個）：54762、25476、76254
• 奇数になる回転（2個）：62547、47625

入力例2

入力： N = 3571

出力：

• 奇数になる回転の個数：4
• 偶数になる回転の個数：0

解説： 回転によって生成される数は以下の4つです。

3571、1357、7135、5713

• 偶数になる回転：なし（0個）
• 奇数になる回転（4個）：3571、1357、7135、5713

アルゴリズムの考え方

ある数が奇数か偶数かは、一の位（最下位の桁）を見れば判定できます。そして、数値を回転させていくと、すべての桁が順番に一の位に現れます。

つまり、「偶数の桁がいくつあるか」が偶数回転の個数に、「奇数の桁がいくつあるか」が奇数回転の個数に等しくなります。したがって、実際にすべての回転を生成する必要はなく、数値を10で割りながら一の位を取り出し、その偶奇を判定してカウントを増やしていけばよいことになります。

処理の手順

• 整数Nとして数値を受け取ります。
• 関数 Even_Odd_rotation(int N) が数値Nを受け取り、奇数回転と偶数回転の個数を出力します。
• カウンターとして Even_rotation（偶数用）と Odd_rotation（奇数用）を0で初期化します。
• do-whileループの中で value = N % 10 により一の位を取り出します。
• value % 2 == 0 なら偶数なので Even_rotation をインクリメントし、そうでなければ Odd_rotation をインクリメントします。
• N = N / 10 として次の桁へ移動します。
• ループ終了後、Even_rotation を偶数回転の個数として出力します。
• 同様に、Odd_rotation を奇数回転の個数として出力します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void Even_Odd_rotation(int N){
    int Even_rotation = 0;
    int Odd_rotation = 0;
    do{
        int value = N % 10;
        if(value % 2 == 1)
            { Odd_rotation++; }
        else
            { Even_rotation++; }
        N = N / 10;
    } while(N != 0);
    cout<<"Count of rotations of N which are Odd are: "<<Odd_rotation;
    cout<<"\nCount of rotations of N which are Even are: "<<Even_rotation;
}
int main(){
    int N = 341;
    Even_Odd_rotation(N);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of rotations of N which are Odd are: 2
Count of rotations of N which are Even are: 1

まとめ

この方法のポイントは、「数の偶奇は一の位だけで決まる」という性質を利用することです。これにより、すべての回転を実際に生成することなく、桁数分の計算（O(桁数)）だけで奇数回転・偶数回転の個数を効率的に求めることができます。