C++で同じ数のセットビットを持つ連続する配列要素の最大数

ソートされていない整数要素の配列が与えられ、タスクは2つの主要なものを計算することです。つまり

• 同じビット数の要素
• また、同じセットビットを持つ要素は本質的に連続している必要があります。

入力

int arr[] = { 5, 8, 1, 2, 9, 12}

出力 −同じセットビット数の連続する配列要素の最大数は− 3

説明 −配列の要素の2進数を計算し、それらのセットビットを計算します。

arr[0] = 5 => 0101 => total set bits are -: 2
arr[1] = 8 => 1000 => total set bits are -: 1
arr[2] = 1 => 0001 => total set bits are -: 1
arr[3] = 2 => 0010 => total set bits are -: 1
arr[4] = 9 => 1001 => total set bits are -: 2
Arr[5] = 12 => 1100 => total set bits are -: 2

したがって、同じ数のセットビットを持ち、本質的に連続している要素は5、9、および12です。したがって、同じ数のセットビットを持つ連続している配列要素の最大数は3です

入力 − int arr [] ={5、8、1、2}

出力 −同じセットビット数の連続する配列要素の最大数は− 2

説明 −配列の要素の2進数を計算し、それらのセットビットを計算します。

arr[0] = 5 => 0101 => total set bits are -: 2
arr[1] = 8 => 1000 => total set bits are -: 1
arr[2] = 1 => 0001 => total set bits are -: 1
arr[3] = 2 => 0010 => total set bits are -: 1

したがって、同じ数のセットビットを持ち、本質的に連続している要素は1と2です。したがって、同じ数のセットビットを持つ連続している配列要素の最大数は2です

以下のプログラムで使用されているアプローチは次のとおりです

• 整数型の配列要素を入力します

• size関数を使用して配列のサイズを計算し、それを関数に渡します

• 一時変数を取得し、値1に設定し、値1の最大変数にも設定します。

• ベクトル型の可変vecを作成する

• 0から配列のサイズまでのループを開始します

• 「__builtin_popcount（element）」関数を使用して配列要素のバイナリセットビットを計算します。この関数は、渡された特定の要素のセットビットの総数を返し、カウントをベクトルに格納し続けます。

• 1からベクトルのサイズまでのループを開始します

• ベクトル内で、vec [i + 1] =vec [i]かどうかを確認してから、tempの値を1ずつインクリメントします

• それ以外の場合は、温度を1に設定します

• maxfunctionを使用してtempとmaximumの間の最大値を選択して最大値を設定します。

• 最大変数を返す

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
//function to calculate maximum same number of bits
int maximum_SameBits(int arr[], int size){
   int temp = 1;
   int maximum = 1;
   vector<int> vec;
   for (int i = 0; i < size; i++){
      vec.push_back(__builtin_popcount(arr[i]));
   }
   for (int i = 1; i < vec.size(); i++){
      if (vec[i + 1] == vec[i]){
         temp++;
      }
      else{
         temp = 1;
      }
      maximum = max(maximum, temp);
   }
   return maximum;
}
int main(){
   int arr[] = { 5, 8, 1, 2, 9, 12};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum number of contiguous array elements with same number of set bits are:
   "<<maximum_SameBits(arr, size);
   return 0;
}

出力

Maximum number of contiguous array elements with same number of set bits are: 3