C++ में बाइनरी सरणी के उपसरणी के दशमलव मान के लिए क्वेरीज़

समस्या विवरण

इस समस्या में, हमें एक बाइनरी सरणी bin[] और Q क्वेरीज़ दी गई हैं जिनमें से प्रत्येक में दो मान L और R होते हैं। हमारा कार्य C++ में बाइनरी सरणी के उपसरणी के दशमलव मान के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।

यहां प्रत्येक क्वेरी को हल करने के लिए, हमें L से R से शुरू होने वाले उपसरणी द्वारा बनाई गई दशमलव संख्या को ढूंढना और प्रिंट करना होगा यानी उपसरणी[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 << "क्वेरी " << (i+1) << ": उपसरणी का दशमलव मान " << CalcDecimalValue(bin, query[i][0], query[i][1]) << "\n";
    }
    return 0;
}

आउटपुट

क्वेरी 1: उपसरणी का दशमलव मान 2
क्वेरी 2: उपसरणी का दशमलव मान 101

दूसरा दृष्टिकोण समस्या को हल करने के लिए पूर्व-गणना सरणी का उपयोग करना है। हम एक पूर्व-गणना सरणी बनाएंगे जो (n-i)वें इंडेक्स मान तक बनी दशमलव संख्या को संग्रहीत करेगी। और क्वेरीज़ को हल करने के लिए, हम 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 << "क्वेरी " << (i+1) << ": उपसरणी का दशमलव मान " << CalcDecimalValue(query[i][0], query[i][1], n) << "\n";
    }
    return 0;
}

आउटपुट

क्वेरी 1: उपसरणी का दशमलव मान 2
क्वेरी 2: उपसरणी का दशमलव मान 101