C ++中二进制数组的子数组的十进制值查询

在这个问题中，我们给了二进制数组bin []和Q查询，每个查询都包含两个值L和R。我们的任务是创建一个程序来解决C ++中二进制数组的子数组的十进制值查询。

问题描述-在这里，为了解决每个查询，我们将不得不查找并打印由从L到R的子数组（即subarray [L ... R]）创建的十进制数。

让我们举个例子来了解这个问题，

输入值

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

输出结果

2 101

说明

对于查询1，形成的子数组为{0，0，1，0}。它将创建二进制数字0010，其十进制转换为2。

对于查询2，形成的子数组为{1，1，0，0，1，0，1}。它将创建二进制数1100101，其十进制转换为101。

解决方法

一个简单的解决方案是通过将二进制字符串从索引L遍历到索引R，找到形成的二进制数，然后将给定的二进制数转换为其等效的十进制数。

程序展示了我们方法的实施

示例

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

输出结果

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

解决该问题的另一种方法是使用预先计算的数组。我们将创建一个预先计算的数组，该数组将存储创建的十进制数，直到第(ni)个索引值为止。对于求解查询，我们将发现l和r的值之间的差异。

数组的第i个值将使用二进制到十进制的转换公式找到。从右侧（即n-1）开始应用

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

该程序说明了我们解决方案的工作原理，

示例

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

输出结果

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