Truy vấn giá trị thập phân của mảng con của mảng nhị phân trong C ++

Mô tả sự cố - Ở đây để giải quyết mỗi truy vấn, chúng ta sẽ phải tìm và in ra số thập phân được tạo bởi mảng con bắt đầu từ L đến R tức là mảng con [L ... R].

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6

Đầu ra

2 101

Giải thích

Đối với truy vấn 1, mảng con được hình thành là {0, 0, 1, 0}. Nó sẽ tạo ra số nhị phân 0010 có chuyển đổi thập phân là 2.

Đối với truy vấn 2, mảng con được hình thành là {1, 1, 0, 0, 1, 0, 1}. Nó sẽ tạo ra số nhị phân 1100101 có chuyển đổi thập phân là 101.

Cách tiếp cận giải pháp

Một giải pháp đơn giản là bằng cách duyệt qua chuỗi nhị phân từ chỉ số L sang chỉ số R, tìm số nhị phân được tạo thành, sau đó chuyển đổi số nhị phân đã cho thành số tương đương thập phân của nó.

Chương trình thể hiện việc triển khai phương pháp tiếp cận của chúng tôi

Ví dụ

#include <iostream>
#include <math.h>
using namespace std;

int CalcDecimalValue(int bin[], int L, int R) {
   int decimal = 0;
   int j = 0;
   for(int i = R; i >= L; i--){
      decimal += bin[i] * pow(2, j);
      j++;
   }
   return decimal;
}

int main() {
   
   int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
   int n = sizeof(bin) / sizeof(bin[0]);
   int Q = 2;
   int query[Q][2] = {{2, 5},{0, 6}};
   for(int i = 0; i < Q; i++){
      cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(bin, query[i]   [0], query[i][1])<<"\n";
   }
   return 0;
}

Đầu ra

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101

Một cách tiếp cận khác để giải quyết vấn đề bằng cách sử dụng một mảng được tính toán trước. Chúng tôi sẽ tạo một mảng được tính toán trước sẽ lưu trữ số thập phân được tạo cho đến giá trị chỉ số thứ (n-i). Và để giải quyết các truy vấn, chúng ta sẽ tìm thấy sự khác biệt giữa giá trị tại l và r.

Giá trị thứ i của mảng sẽ được tìm thấy bằng cách sử dụng công thức chuyển đổi từ nhị phân sang thập phân. Áp dụng nó từ phía bên phải, tức là từ n-1,

decimalArray [i] =bin [i] * 2 ^ (n-1-i) + bin [i + 1] * 2 ^ (n-1-i + 1) +… bin [n-1] * 2 ^ ( 0).

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int decimalArray[1000];

void createDecimalArray(int bin[], int n){
   memset(decimalArray, 0, n*sizeof(int));
   decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
   for (int i = n - 2; i >= 0; i--)
   decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2,(n - 1 - i)));
}

int CalcDecimalValue(int L, int R, int n){
   if (R != n - 1)
   return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
   return decimalArray[L] / (1 << (n - 1 - R));
}

int main(){

   int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
   int n = sizeof(bin) / sizeof(bin[0]);
   createDecimalArray(bin, n);
   int Q = 2;
   int query[Q][2] = {{2, 5},{0, 6}};
   for(int i = 0; i < Q; i++){
      cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(query[i][0],    query[i][1], n)<<"\n";
   }
   return 0;
}

Đầu ra

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101