K번째 비트가 설정된 범위의 배열 요소 수를 쿼리하기 위해 C++로 작성된 코드

이 글에서는 주어진 범위에서 −

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

와 같이 k번째 비트가 설정된 요소 수를 찾는 문제에 대해 논의할 것입니다. 이 문제를 무차별 대입 방식으로 해결하고 이 접근 방식이 작동하는지 확인하겠습니다. 더 높은 제약 조건을 위해. 만약 작동하지 않는다면, 우리는 새로운 효율적인 방법을 생각해내려고 노력합니다.

무차별 대입 방법

이 방법에서는 범위를 반복하고 각 요소의 k번째 비트가 설정되었는지 확인한 다음 그렇다면 개수를 증가시킵니다.

Example

#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

위 방법의 시간 복잡도는 O(N*Q)입니다. 여기서 N은 배열의 크기이고 Q는 주어진 쿼리 수입니다. 이 방법은 다음과 같습니다. better for high 시간이 너무 오래 걸리기 때문에 제약이 적용되지 않으므로 이제 효율적인 프로그램을 만들어보도록 하겠습니다.

효율적인 방법

이 방법에서는 각 인덱스 위치에 사용되는 비트 수를 보유하는 2D 접두어 합계 배열을 유지하고 이를 O(1) 복잡도로 계산할 수 있습니다.

Example

#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

O(1) 시간 복잡도에서 답을 찾는 데 도움이 되는 접두사 배열을 유지하고 있으므로 시간 복잡도는 O(N)으로 크게 줄어듭니다. 여기서 N은 주어진 크기입니다. 배열의.

위 코드 설명

이 프로그램에서는 배열의 각 인덱스에 대한 접두사 카운터를 유지 관리하며 해당 인덱스 이전에 사용된 각 비트 수를 계산합니다. 이제 각 숫자의 접두사 개수를 저장했으므로 k 번째 개수의 경우 R 번째 인덱스 Count의 k 번째 접두사 개수에서 L-1 인덱스의 k 번째 접두사 개수를 빼야 합니다. 그것이 우리의 대답입니다.

결론

이 기사에서는 K번째 비트 세트를 사용하여 다양한 배열 요소에 대한 쿼리를 해결하는 문제를 다루었습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(사소하고 효율적인)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 K번째 비트가 설정된 범위의 배열 요소 수를 쿼리하기 위해 C++로 작성된 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!