C++で配列のarr[i] % arr[j]の最大値を効率的に求める方法

この問題では、n個の要素からなる配列が与えられます。与えられた配列に対して、arr[i] % arr[j] の最大値を求めるプログラムを作成するのが課題です。

つまり、配列内の2つの要素を割り算したときに生じる余りの中から、最大のものを見つける必要があります。

具体例を使って問題を理解しましょう。

入力 − array {3, 6, 9, 2, 1}

出力 − 6

説明 − 配列内のすべてのペアについて余りを計算すると、以下のようになります。

3 % 3 = 0; 3 % 6 = 3; 3 % 9 = 3; 3 % 2 = 1; 3 % 1 = 0
6 % 3 = 0; 6 % 6 = 0; 6 % 9 = 6; 6 % 2 = 0; 6 % 1 = 0
9 % 3 = 0; 9 % 6 = 3; 9 % 9 = 0; 9 % 2 = 1; 9 % 1 = 0
2 % 3 = 2; 2 % 6 = 2; 2 % 9 = 2; 2 % 2 = 0; 2 % 1 = 0
1 % 3 = 1; 1 % 6 = 1; 1 % 9 = 1; 1 % 2 = 1; 1 % 1 = 0
これらの余りの中で最大の値は 6 です。

素朴なアプローチ:すべてのペアを調べる

この問題への最も直接的な解法は、配列内のすべての要素のペアについて余りを計算し、その中から最大値を見つけることです。しかし、この方法ではすべての組み合わせを調べる必要があるため、時間計算量が O(n²) となり、配列のサイズが大きくなると実用的ではなくなります。

効率的なアプローチ:ソートを活用する

より効率的な解法は、剰余演算の性質を利用します。x % y は y > x のときに x そのものとなり、これが取り得る最大の余りです。したがって、配列の中で最大の要素を割る数(除数)とし、2番目に大きい要素を割られる数(被除数)とすれば、結果が最大になります。

この性質を踏まえると、手順は次の通りです。

1. 配列を昇順にソートする。
2. すべての要素が同じ値の場合は、どの組み合わせでも余りが 0 になるため 0 を返す。
3. それ以外の場合は、ソート後の配列の最後から2番目の要素(arr[n-2])を答えとして返す。

この方法の時間計算量はソートに要する O(n log n) であり、全ペアを調べる O(n²) と比べて大幅に効率化できます。

実装例

上記の解法をC++で実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int maxRemainder(int arr[], int n){
    bool hasSameValues = true;
    for(int i = 1; i<n; i++) {
        if (arr[i] != arr[i - 1]) {
            hasSameValues = false;
            break;
        }
    }
    if (hasSameValues)
        return 0;
    sort(arr, arr+n);
    return arr[n-2];
}
int main(){
    int arr[] = { 3, 6, 9, 2, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum remainder on dividing two elements of the array is "<<maxRemainder(arr, n);
    return 0;
}

出力

The maximum remainder on dividing two elements of the array is 6

このプログラムでは、まず配列内のすべての要素が同一かどうかを確認し、同一であれば 0 を返します。異なる値が含まれる場合は配列をソートし、2番目に大きい要素を最大の余りとして返します。入力配列 {3, 6, 9, 2, 1} の場合、最大要素は 9、2番目に大きい要素は 6 なので、6 % 9 = 6 が最大の余りとなります。