C++でa[i]×a[j]の積が2の累乗になる非順序対（i, j）を数える方法

問題の概要

N個の要素からなる配列が与えられたとき、積が2の累乗（1, 2, 4, 8, 16, …）になるようなすべてのペア（Arr[i], Arr[j]）の個数を求めます。ここで i ≠ j とします。つまり、Arr[i] × Arr[j] が2の累乗となるインデックスの組み合わせをカウントするのが目的です。

判定には対数を利用します。ある正の整数 prod が2の累乗であるかどうかは、log2(prod) が整数かどうかで確認できます。具体的には、ceil(log2(prod)) と floor(log2(prod)) が等しければ、prod は2の累乗であると判断できます。

入出力例

入力： Arr[] = { 4, 3, 2, 1, 2, 4 }、N = 6

出力： 積が2の累乗となるペアの数： 10

説明：

Arr[0]×Arr[2]=8、Arr[0]×Arr[3]=4、Arr[0]×Arr[4]=8、Arr[0]×Arr[5]=16
Arr[2]×Arr[3]=2、Arr[2]×Arr[4]=4、Arr[2]×Arr[5]=8
Arr[3]×Arr[4]=2、Arr[3]×Arr[5]=4、Arr[4]×Arr[5]=8
これら10組の積はすべて2の累乗です。

入力： Arr[] = { 3, 3, 3, 3, 3 }、N = 5

出力： 積が2の累乗となるペアの数： 0

説明： すべてのペアの積は9となり、2の累乗ではありません。

プログラムで使用するアプローチ

• ランダムな値で初期化された整数型配列 Arr[] を用意します。

• 配列の長さを格納する変数 n を定義します。

• 関数 countPairs(int arr[], int n) は、配列とその長さを引数として受け取り、積が2の累乗となるペアの数を返します。

• 2重のforループで配列を走査し、各ペアを調べます。

• 外側のループは 0 ≤ i < n-1、内側のループは i < j < n の範囲で実行します。

• arr[i] と arr[j] の積 prod を計算します。

• ceil(log2(prod)) == floor(log2(prod)) が成り立つか確認します。成り立てば prod は2の累乗なので、カウントを1増やします。

• すべてのループが終了した時点で、count には条件を満たすペアの総数が格納されています。

• count を結果として返します。

なお、配列に0が含まれる場合、log2(0) は未定義となるため注意が必要です。実運用では prod > 0 のチェックを追加しておくと安全です。

C++実装例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
    int count=0;
    int prod=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            prod=arr[i]*arr[j];
            if( ceil(log2(prod))==floor(log2(prod)) ){
                count++;
                //cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //表示用
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 2, 5, 8, 16, 128 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout <<endl<<"Pairs whose product is power of 2:"<<countPairs(arr, n);
    return 0;
}

出力結果

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

Pairs whose product is power of 2:6

配列 { 2, 5, 8, 16, 128 } の場合、積が2の累乗になるペアは以下の6組です。

• 2×8 = 16
• 2×16 = 32
• 2×128 = 256
• 8×16 = 128
• 8×128 = 1024
• 16×128 = 2048