Hello Everyone,
Given a binary array arr[], we to find the number represented by the subarray a[l…r]. There are multiple such queries.
Examples:
Input : arr[] = {1, 0, 1, 0, 1, 1};
l = 2, r = 4
l = 4, r = 5
Output : 5
3
Subarray 2 to 4 is 101 which is 5 in decimal.
Subarray 4 to 5 is 11 which is 3 in decimal.
Input : arr[] = {1, 1, 1}
l = 0, r = 2
l = 1, r = 2
Output : 7
3
A Simple Solution is to compute decimal value for every given range using simple binary to decimal conversion. Here each query takes O(len) time where len is length of range.
An Efficient Solution is to do per-computations, so that queries can be answered in O(1) time.
The number represented by subarray arr[l…r] is arr[l]*2^{r-l} + arr[l+1]*2^{r - l - 1} …… + arr[r]*2^{r-r}
- Make an array pre[] of same size as of given array where pre[i] stores the sum of arr[j]*2^{n - 1 - j} where j includes each value from i to n-1.
- The number represented by subarray arr[l…r] will be equal to (pre[l] – pre[r+1])/2^{n-1-r} . pre[l] – pre[r+1] is equal to arr[l]*2^{n - 1 - l} + arr[l+1]*2^{n - 1 - l - 1} +……arr[r]*2^{n - 1 - r} . So if we divide it by 2^{n - 1 - r} , we get the required answer
// C++ implementation of finding number
// represented by binary subarray
#include <bits/stdc++.h>
using
namespace
std;
// Fills pre[]
void
precompute(
int
arr[],
int
n,
int
pre[])
{
memset
(pre, 0, n *
sizeof
(
int
));
pre[n - 1] = arr[n - 1] *
pow
(2, 0);
for
(
int
i = n - 2; i >= 0; i--)
pre[i] = pre[i + 1] + arr[i] * (1 << (n - 1 - i));
}
// returns the number represented by a binary
// subarray l to r
int
decimalOfSubarr(
int
arr[],
int
l,
int
r,
int
n,
int
pre[])
{
// if r is equal to n-1 r+1 does not exist
if
(r != n - 1)
return
(pre[l] - pre[r + 1]) / (1 << (n - 1 - r));
return
pre[l] / (1 << (n - 1 - r));
}
// Driver Function
int
main()
{
int
arr[] = { 1, 0, 1, 0, 1, 1 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
int
pre[n];
precompute(arr, n, pre);
cout << decimalOfSubarr(arr, 2, 4, n, pre) << endl;
cout << decimalOfSubarr(arr, 4, 5, n, pre) << endl;
return
0;
}
Output:
5
3