Dãy số tự đồng nhất (Automorphic) liên tiếp dài nhất trong C++

Số tự đồng nhất (Automorphic) là số mà bình phương của nó kết thúc bằng chính số đó. Ví dụ: 5²=25, 6²=36, 25²=625, 76²=5776.

Cho mảng arr[] kích thước N. Tìm độ dài dãy con liên tiếp dài nhất chỉ chứa số tự đồng nhất.

Ví dụ

arr = {5, 3, 625, 6, 8, 1} → Output: 2 (dãy {625, 6})
arr = {33, 25, 1, 76, 4} → Output: 3 (dãy {25, 1, 76})

Kiểm tra số tự đồng nhất

Số n là tự động nhất ⇔ n² % 10^k == n với k là số chữ số của n.

Cách kiểm tra: so sánh từng chữ số từ cuối của n và n².

Thuật toán

• Duyệt mảng, giữ currentLen (độ dài dãy tự đồng nhất hiện tại) và maxLen (tối đa).
• Nếu arr[i] tự đồng nhất: currentLen++, cập nhật maxLen.
• Ngược lại: currentLen = 0.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

bool isAutomorphic(int n) {
    if (n < 0) return false;
    long long sq = 1LL * n * n;
    while (n > 0) {
        if (n % 10 != sq % 10) return false;
        n /= 10;
        sq /= 10;
    }
    return true;
}

int maxAutomorphicSubarray(int arr[], int n) {
    int cur = 0, best = 0;
    for (int i = 0; i < n; i++) {
        if (isAutomorphic(arr[i])) {
            cur++;
            best = max(best, cur);
        } else cur = 0;
    }
    return best;
}

int main() {
    int arr[] = {33, 25, 1, 76, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxAutomorphicSubarray(arr, n); // Output: 3
    return 0;
}

Kết quả

3