C++で配列内の連続する自己同形数の最大個数を求める方法

問題の概要

N個の要素からなる配列が与えられたとき、その中で連続して現れる自己同形数の最大個数を求めるのが本記事のテーマです。

まず、自己同形数（Automorphic Number）とは何かを確認しましょう。自己同形数とは、その数を2乗した結果（平方数）の下位の桁が、元の数と一致する数のことです。例えば、5は5×5=25となり、25の下一桁が「5」で元の数と一致するため、自己同形数です。

入力例と出力例

入力： arr[] = {5, 3, 625, 6, 8, 1}

出力： 2

説明： この配列に含まれる自己同形数は「5」「625」「6」「1」ですが、隣り合って連続している自己同形数の中で最も長いのは「625」と「6」のペアです。そのため出力は2になります。

入力： arr[] = {33, 25, 1, 76, 4}

出力： 3

説明： この配列では「25」（25²=625）、「1」、「76」（76²=5776）がすべて自己同形数であり、これらが連続して並んでいるため、最大連続長は3となります。

アルゴリズムの考え方

このプログラムでは、以下の手順で問題を解きます。

• main()関数内でint型の変数sizeを用意し、与えられた配列のサイズを格納します。
• MaxAutomorphic()関数内で、現在の連続カウントを表すCurrentMaxと、これまでの最大連続長を表すMaximumを、ともにint型で0に初期化します。
• i=0からi<nまでループ処理を行い、IsAutomorphic()関数を呼び出して各要素が自己同形数かどうかを判定します。
• IsAutomorphic()関数内では、nの2乗を格納するint型変数sqr = n * nを用意します。
• whileループ（条件： n > 0）でnとsqrの下一桁を順番に比較することで、その数が自己同形数かどうかを調べます。
• MaxAutomorphic()関数に処理を戻し、要素が自己同形数でない場合はCurrentMaxを0にリセットします。
• 逆に自己同形数であった場合はCurrentMaxに1を加算し、CurrentMaxとMaximumのうち大きい方の値をMaximumに更新します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 数が自己同形数かどうかを判定する関数
bool IsAutomorphic(int n){
    // nの2乗を格納する
    int sqr = n * n;
    // 各桁を比較する
    while (n > 0){
        /* nのいずれかの桁が2乗の下位桁と
        一致しない場合はfalseを返す */
        if (n % 10 != sqr % 10)
            return false;
        n /= 10;
        sqr /= 10;
    }
    return true;
}
int MaxAutomorphic(int arr[], int size){
    int CurrentMax = 0, Maximum = 0;
    for (int i = 0; i < size; i++){
        // 要素が自己同形数でない場合
        if (IsAutomorphic(arr[i]) == false)
            CurrentMax = 0;
        // 自己同形数の場合はCurrentMaxとMaximumを更新する
        else{
            CurrentMax++;
            Maximum = max(CurrentMax, Maximum);
        }
    }
    return Maximum;
}
// メイン関数
int main(){
    int arr[] = { 33, 25, 1, 76, 4 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << MaxAutomorphic(arr, size);
    return 0;
}

実行結果

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

3

計算量について

配列の各要素に対する自己同形数の判定は、桁数に比例した時間で行われます。したがって、全体の時間計算量はO(N・d)（Nは要素数、dは数値の平均桁数）、追加で必要となる空間計算量はO(1)と非常に効率的です。