C言語で配列内の最大AND値ペアを出力するプログラム

問題の概要

この問題では、n個の正の整数からなる配列が与えられ、その中から最大のAND値を持つペアを見つける必要があります。

例

入力: arr[] = { 4, 8, 12, 16 }
出力: pair = 8 12
最大AND値 = 8

入力: arr[] = { 4, 8, 16, 2 }
出力: pair = No possible AND
最大AND値 = 0

アプローチ

最大AND値の求め方は、配列内の最大AND値を求める問題と基本的な考え方は同じです。ただし、このプログラムでは、その最大AND値を実際に生み出す要素のペアまで特定する必要があります。

要素を特定するには、配列全体を走査し、各要素と求めた最大AND値(res)とのAND演算を計算します。arr[i] & result == result が成立する場合、arr[i] は最大AND値を生成する要素のひとつであることを意味します。また、最大AND値(res)が0になった場合は、条件を満たすペアが存在しないため「No possible AND(ペアなし)」と出力します。

アルゴリズムのポイント

このアルゴリズムは、上位ビットから順に確認していく貪欲法を採用しています。31ビット目から0ビット目に向かって、そのビットを立てたパターンとのAND値がパターンと一致する要素が2つ以上存在するかを確認し、存在すればそのビットを結果に加えます。これにより、効率的に最大AND値を構築できます。

アルゴリズム

int checkBit(int pattern, int arr[], int n)
開始
手順1: count を宣言し 0 で初期化
手順2: i = 0 から i < n まで i++ でループ
    もし (pattern & arr[i]) == pattern ならば、
        count を 1 増やす
手順3: count を返す
終了

int maxAND(int arr[], int n)
開始
手順1: res = 0 と count を宣言・初期化
手順2: bit = 31 から bit >= 0 まで bit-- でループ
    count = checkBit(res | (1 << bit), arr, n) を呼び出す
    もし count >= 2 ならば、
        res |= (1 << bit)
    終了
    もし res == 0 ならば
        「no possible AND」と出力
    それ以外ならば
        「Pair with maximum AND= 」と出力
    count = 0
    i = 0 から i < n かつ count < 2 の間 i++ でループ
        もし (arr[i] & res) == res ならば、
            count を 1 増やす
            arr[i] を出力
        終了
    ループ終了
ループ終了
res を返す
終了

サンプルコード

#include <stdio.h>
int checkBit(int pattern, int arr[], int n){
    int count = 0;
    for (int i = 0; i < n; i++)
        if ((pattern & arr[i]) == pattern)
            count++;
    return count;
}
// 最大AND値ペアを見つける関数
int maxAND(int arr[], int n){
    int res = 0, count;
    for (int bit = 31; bit >= 0; bit--) {
        count = checkBit(res | (1 << bit), arr, n);
        if (count >= 2)
            res |= (1 << bit);
    }
    if (res == 0) // ペアが存在しない場合
        printf("no possible and\n");
    else { // 見つかったペアを出力
        printf("Pair with maximum AND= ");
        count = 0;
        for (int i = 0; i < n && count < 2; i++) {
            // 要素を出力後に count を増加
            if ((arr[i] & res) == res) {
                count++;
                printf("%d ", arr[i]);
            }
        }
    }
    return res;
}
int main(int argc, char const *argv[]){
    int arr[] = {5, 6, 2, 8, 9, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    int ma = maxAND(arr, n);
    printf("\nThe maximum AND value= %d ", ma);
    return 0;
}

出力

上記のプログラムを実行すると、以下の出力が得られます。

pair = 8 9
The maximum and value= 8

計算量

時間計算量: O(n × 32) ― 最大32ビットそれぞれについて配列を走査するため、実質的に O(n) に近い効率で動作します。
空間計算量: O(1) ― 追加のメモリは定数個の変数のみで済みます。