K 番目のビットが設定されている範囲内の配列要素の数をクエリするために C++ で記述されたコード

この記事では、指定された範囲内で k 番目のビットが設定されている要素の数を見つける問題について説明します (例: −

Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
   0
   1

)。 pass この問題に対する強引なアプローチを実行し、このアプローチがより高い制約で機能するかどうかを確認します。それがうまくいかない場合は、新しい効率的な方法を考えようとします。

ブルート フォース メソッド

このメソッドでは、範囲を反復処理して、各要素の k 番目のビットが設定されているかどうかを確認し、設定されている場合はカウントをインクリメントします。

例

#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
   if (n & (1 << (k - 1)))
   return true;
   return false;
}
int query(int L, int R, int K, int arr[]) {
   int count = 0; // counter to keep count of number present in the range
   for (int i = L; i <= R; i++) { // traversing the range
      if (Kset(arr[i], K)) {
         count++;
      }
   }
   return count;
}
int main() {
   int arr[] = { 4, 5, 7, 2 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int queries[][3] = { // given L, R and k
      { 2, 4, 4 },
      { 3, 5, 1 }
   };
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries

   for (int i = 0; i < q; i++) {
      int L = queries[i][0] - 1;
      int R = queries[i][1] - 1;
      int K = queries[i][2];

      cout << query(L, R, K, arr) << "\n";
   }
   return 0;
}

出力

0
1

上記のメソッドの時間計算量は O(N*Q) です。ここで、N は配列のサイズ、Q は指定された値です。ご覧のとおり、このアプローチは時間がかかりすぎるため、より高い制約では機能しません。そこで、効率的なプログラムを作成してみます。

効率的な方法

この方法では、各インデックス位置で使用されるビット数を維持する 2D プレフィックス合計配列を維持します。これを O( 答えは次のように計算されます) で実行できます。 1) の複雑さ。

例

#include<bits/stdc++.h>
using namespace std;
#define bits 32 // number of bits

int P[100000][bits+1];

bool Kset(int n, int k) {
   if (n & (1 << (k - 1)))
      return true;
   return false;
}
void prefixArray(int n, int arr[]) { // building the prefix array
   for (int i = 0; i <= bits; i++) {
      P[0][i] = 0; // setting every bits initial count = 0
   }
   for (int i = 0; i < n; i++) {
      for (int j = 1; j <= bits; j++) {
         bool flag = Kset(arr[i], j);
         if (i) // we add previous count to the latest count(0)
            P[i][j] = P[i - 1][j];
         if (flag) { // if jth bit is set so we increase the count
            P[i][j]++;
         }
      }
   }
}
int query(int L, int R, int K) {
   if (L) // if L not equal to 0 then we return the prefix at R subtracted with prefix at L-1
      return P[R][K] - P[L - 1][K];
   else
      return P[R][K];
}
int main() {
   int arr[] = { 8, 9, 1, 3 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of given array
   int queries[][3] = {
      { 1, 3, 4 },
      { 2, 4, 1 }
   };
   prefixArray(n, arr); // calling the function to create prefix array
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries

   for (int i = 0; i < q; i++) {
      int L = queries[i][0] - 1;
      int R = queries[i][1] - 1;
      int K = queries[i][2];
      cout << query(L, R, K) << "\n";
   }
   return 0;
}

出力

2
3

O(1)の時間計算量で答えを見つけるのに役立つプレフィックス配列を維持しているため、時間計算量は大幅に増加します。は O(N) に縮小されます。ここで、N は指定された配列のサイズです。

上記のコードの説明

このプログラムでは、配列のインデックスごとにプレフィックス カウンターを維持します。これは、そのインデックスの前で使用される各ビット数をカウントするために使用されます。ここで、各桁のプレフィックス カウントを保存したので、k 番目のカウントについては、R 番目のインデックスの k 番目のプレフィックス カウントから、L-1 インデックスの k 番目のプレフィックスを減算する必要があります。それが私たちの答えです。

結論

この記事では、K 番目のビットが設定された配列要素の範囲に対するクエリを解く問題について説明しました。また、この問題に対する C プログラムと、それを解決するための完全なアプローチ (簡単かつ効率的な) についても学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がK 番目のビットが設定されている範囲内の配列要素の数をクエリするために C++ で記述されたコードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。