C++でmatrix(i, j) = i+jとなるn×n行列内のkの出現回数をカウントする方法

整数値で構成される行列が与えられ、その中に特定の整数 k が何回出現するかをカウントすることが課題です。行列のサイズは任意に設定できますが、本記事では 4×4 の行列を例に解説します。行列は matrix(i, j) = i + j という条件に基づいて生成され、インデックスは 0 から始まるため、matrix[0][0] = 0 となります。

入出力例

例1

入力: int size = 4, k = 4

出力: 4×4 の行列における 4 の出現回数は 3

説明:

matrix[i][j] = i + j（i = j = 4）
Matrix[4][4] = {
    0, 1, 2, 3
    1, 2, 3, 4
    2, 3, 4, 5
    3, 4, 5, 6
}
数値 k（= 4）はこの行列の中に 3 回出現します。

例2

入力: int size = 3, k = 1

出力: 3×3 の行列における 1 の出現回数は 2

説明:

matrix[i][j] = i + j（i = j = 3）
Matrix[3][3] = {
    0, 1, 2
    1, 2, 3
    2, 3, 4
}
数値 k（= 1）はこの行列の中に 2 回出現します。

アルゴリズムの考え方

• n × n 行列のサイズと、探索対象となる整数値 k を入力として受け取る
• 外側のループ変数 i を 0 から行サイズまで繰り返す
• 内側のループ変数 j を 0 から列サイズまで繰り返す
• 各要素に matrix[i][j] = i + j を代入する
• matrix[i][j] が k と等しいかどうかを判定する
• 一致していればカウントを 1 増やし、一致しなければそのまま次の要素へ進む
• すべての走査が終わったらカウントを返す
• 結果を出力する

C++ 実装例

#include <iostream>
using namespace std;

int countOccurrences(int size, int k){
    int count = 0;
    int matrix[size][size];
    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            matrix[i][j] = i + j;
            if(matrix[i][j] == k){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int size = 4;
    int k = 4;
    int total = countOccurrences(size, k);
    if(total > 0){
        cout << "Count of frequency of " << k << " in a matrix of size "
             << size << "X" << size << " where matrix(i, j) = i+j is: " << total;
    } else {
        cout << "Frequency of element is 0 that means it is not present in a matrix";
    }
}

出力結果

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

Count of frequency of 4 in a matrix of size 4X4 where matrix(i, j) = i+j is: 3

補足： 計算量と数学的なアプローチ

この方法の時間計算量・空間計算量はどちらも O(n²) です。しかし、この行列には規則性があるため、行列を実際に生成せずに数学的に答えを求めることも可能です。値 k が出現するセルは i + j = k を満たす反対角線上に並んでおり、その出現回数は次の式で表されます。

count(k) = min(k + 1, 2n − 1 − k)　※ 0 ≤ k ≤ 2n − 2 の場合
それ以外の場合は 0

例えば n = 4、k = 4 の場合、min(5, 3) = 3 となり、実際のカウント結果と一致します。大規模な行列を扱う場合には、この数式による O(1) の計算方法が非常に有効です。