এই সমস্যাতে, আমাদের একটি বাইনারি অ্যারে 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
ব্যাখ্যা
কোয়েরি ১-এ, গঠিত সাবঅ্যারে হচ্ছে { 0, 0, 1, 0}। এটি বাইনারি নম্বর 0010 তৈরি করে যার ডেসিমেল রূপান্তর ২।
কোয়েরি ২-এ, গঠিত সাবঅ্যারে হচ্ছে { 1, 1, 0, 0, 1, 0, 1}। এটি বাইনারি নম্বর 1100101 তৈরি করে যার ডেসিমেল রূপান্তর ১০১।
সমাধান পদ্ধতি
একটি সহজ সমাধান হচ্ছে বাইনারি স্ট্রিং-কে ইনডেক্স 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
আরেকটি পদ্ধতি হচ্ছে প্রি-কম্পিউটেড অ্যারে ব্যবহার করা। আমরা একটি প্রি-কম্পিউটেড অ্যারে তৈরি করব যা (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<<"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
