Kod yang ditulis dalam C++ untuk menanyakan bilangan elemen tatasusunan dalam julat yang mempunyai set bit Kth

Dalam artikel ini, kita akan membincangkan masalah mencari bilangan elemen dalam julat tertentu yang mempunyai set bit k-th, seperti −#🎜🎜 #

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

# 🎜🎜#Kami akan menyelesaikan masalah ini melalui kaedah brute force dan melihat sama ada kaedah ini berfungsi untuk kekangan yang lebih tinggi. Jika ia tidak berkesan, maka kita cuba memikirkan kaedah baru yang cekap.

Kaedah Brute Force

Dalam kaedah ini, kita hanya lelaran melalui julat dan semak sama ada bit k setiap elemen ditetapkan dan jika ya, tambahkan kiraan.

Contoh

#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;
}

Output

0
1

Kerumitan masa bagi kaedah di atas ialah O(N*Q), dengan N ialah saiz array, Q ialah bilangan pertanyaan yang diberikan seperti yang anda lihat, pendekatan ini tidak berfungsi untuk kekangan yang lebih tinggi kerana ia akan mengambil masa yang terlalu lama, jadi sekarang kami akan cuba membuat program yang cekap.

Kaedah yang cekap

Dalam kaedah ini, kami akan mengekalkan tatasusunan jumlah awalan dua dimensi yang akan mengekalkan bilangan bit yang digunakan untuk setiap kedudukan indeks, dan kami Jawapannya boleh dikira dalam kerumitan O(1).

Contoh

#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;
}

Output

2
3

Memandangkan kami mengekalkan tatasusunan awalan yang membantu kami mencari jawapan dalam kerumitan masa O(1), jadi Kerumitan masa kami dikurangkan dengan banyak kepada O(N), di mana N ialah saiz tatasusunan yang diberikan.

Penjelasan kod di atas

Dalam program ini, kami mengekalkan pembilang awalan untuk setiap indeks tatasusunan, yang digunakan untuk mengira setiap bilangan bit yang digunakan sebelum indeks itu . Sekarang, kita telah menyimpan kiraan awalan untuk setiap digit, jadi untuk kiraan ke-k, kita perlu menolak awalan ke-k pada indeks L-1 daripada kiraan awalan ke-k pada Kiraan indeks ke-R, itu jawapan kami.

Kesimpulan

Dalam artikel ini, kami menangani masalah menyelesaikan pertanyaan untuk elemen tatasusunan julat dengan set bit Kth. Kami juga mempelajari program C++ untuk masalah ini dan pendekatan lengkap kami untuk menyelesaikannya (kedua-dua remeh dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Kod yang ditulis dalam C++ untuk menanyakan bilangan elemen tatasusunan dalam julat yang mempunyai set bit Kth. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!