इस समस्या में, हमें एक बाइनरी ऐरे बिन [] और क्यू क्वेरीज़ दी जाती हैं, जिनमें से प्रत्येक में दो मान एल और आर होते हैं। हमारा काम सी ++ में बाइनरी एरे के सबएरे के दशमलव मानों के लिए सॉल्व क्वेरीज़ बनाने के लिए एक प्रोग्राम बनाना है। मजबूत> ।
समस्या का विवरण - यहां प्रत्येक क्वेरी को हल करने के लिए, हमें दशमलव संख्या को ढूंढना और प्रिंट करना होगा जो कि एल से आर तक सबअरे द्वारा बनाई गई है यानी सबरे [एल...आर]।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
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 है।
समाधान दृष्टिकोण
एक आसान समाधान इंडेक्स एल से इंडेक्स आर तक बाइनरी स्ट्रिंग को पार करके, बाइनरी नंबर का गठन किया गया है, और फिर दिए गए बाइनरी नंबर को इसके दशमलव समकक्ष में परिवर्तित करें।
हमारे दृष्टिकोण के कार्यान्वयन को दिखाने के लिए कार्यक्रम
उदाहरण
#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
एक और तरीका समस्या को हल करने के लिए पूर्व-गणना सरणी का उपयोग करना है। हम एक प्रीकंप्यूटेड ऐरे बनाएंगे जो (एन-आई)वें इंडेक्स वैल्यू तक बनाए गए दशमलव नंबर को स्टोर करेगा। और प्रश्नों को हल करने के लिए, हम l और r के मान के बीच का अंतर पाएंगे।
सरणी का ith मान बाइनरी से दशमलव रूपान्तरण सूत्र का उपयोग करके पाया जाएगा। इसे दाईं ओर से, यानी n-1 से,
. से लगानादशमलवअरे [i] =बिन [i] * 2 ^ (n-1-i) + बिन [i + 1] * 2 ^ (n-1-i + 1) + … बिन [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