【C++】1を加えることで2の累乗にできる数の個数を求める方法

問題概要

正の整数からなる配列が与えられます。求めたいのは、各要素に対して最大1回だけ「1を加える」という操作を行うことで、2の累乗にすることができる数の個数です。

判定には log2(i) を活用します。2の累乗の対数は必ず整数になるため、floor(log2(i)) と ceil(log2(i)) が一致すれば、その数は2の累乗だと判断できます。この性質を使って、「そのまま2の累乗であるか」「1を加えれば2の累乗になるか」をチェックし、条件を満たすたびにカウントを増やしていきます。

具体例で確認してみましょう。

入出力例

入力: arr[] = {1, 3, 2, 5, 6}

出力: 2の累乗にできる数の個数: 3

説明: 1+1=2(=2¹)、3+1=4(=2²)、そして 2 はもともと 2¹ なので計3個が該当します。残りの要素は 5+1=6、6+1=7 となり、どちらも2の累乗にはなりません。

入力: arr[] = {2, 4, 8, 16}

出力: 2の累乗にできる数の個数: 4

説明: 4つの要素はすべて、すでに2の累乗です。

アルゴリズムの流れ

• ランダムな正の整数で初期化された整数配列 arr[] を用意します。
• 関数 powofTwo(int arr[], int n) は配列とその長さを引数に受け取り、2の累乗であるか、または操作によって2の累乗にできる数の個数を返します。
• カウントの初期値を 0 とします。
• i = 0 から i < n まで配列を先頭から順に走査します。
• 各要素について、floor(log2(arr[i])) == ceil(log2(arr[i]))(arr[i] 自体が2の累乗の場合)または floor(log2(arr[i]+1)) == ceil(log2(arr[i]+1))(arr[i] に1を加えると2の累乗になる場合)が成立するかを確認し、いずれかが真であればカウントを1増やします。
• 最終的な結果として count を返します。

C++による実装例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int powofTwo(int arr[],int n){
    int count=0;
    for(int i=0;i<n;i++){
       if( floor(log2(arr[i])) == ceil(log2(arr[i])) )
           { count++; }
       else{
          ++arr[i];
          if( floor(log2(arr[i])) == ceil(log2(arr[i])) )
              { count++; }
       }
   }
   return count;
}
int main(){
   int Arr[]={ 5,6,9,3,1 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout<<endl<<"Count of numbers with power of 2 possible: "<<powofTwo(Arr,len);
   return 0;
}

実行結果

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

Count of numbers with power of 2 possible: 2

この例では、{5, 6, 9, 3, 1} のうち、9+1=10、5+1=6、6+1=7 では2の累乗になりませんが、3+1=4(=2²)と 1+1=2(=2¹)が該当するため、答えは 2 となります。この手法の計算量は O(n) であり、配列を一度走査するだけで判定が完了するため、非常に効率的です。