C++-এ কোয়েরি অনুযায়ী বামপাশে ০ এবং ১-এর সংখ্যা বের করুন

একটি বাইনারি অ্যারে (শুধু ০ এবং ১) এবং একাধিক কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরি ইনডেক্সের জন্য, সেই ইনডেক্সের বামপাশে (স্ট্রিক্টলি লেস দান) কতটি ০ এবং ১ আছে তা বের করতে হবে।

উদাহরণ

ইনপুট: arr = {0,1,1,1,0,0,0,1,0,0}, queries = {2,4,1,0,5}

আউটপুট:

query 1: zeros = 1, ones = 1
query 2: zeros = 1, ones = 3
query 3: zeros = 1, ones = 0
query 4: zeros = 0, ones = 0
query 5: zeros = 2, ones = 3

অ্যালগরিদম

নেইভ পদ্ধতি (O(q×n))

প্রতিটি কোয়েরির জন্য ০ থেকে query[i]-1 পর্যন্ত লুপ চালিয়ে কাউন্ট করুন। সহজ কিন্তু ধীর।

ইফিশিয়েন্ট পদ্ধতি: প্রিফিক্স সম (O(n+q))

1. একটি ২ডি অ্যারে prefix[i][0] = ইনডেক্স i-এর বামে ০-এর সংখ্যা, prefix[i][1] = ১-এর সংখ্যা।
2. একবার ট্রাভার্স করে প্রিফিক্স বানান।
3. প্রতিটি কোয়েরির জন্য O(1)-এ উত্তর দিন: prefix[query[i]][0] এবং prefix[query[i]][1]।

C++ প্রোগ্রাম (ইফিশিয়েন্ট)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int nums[] = {1,0,0,1,1,0,0,1,0,0};
    int queries[] = {2,4,1,0,5};
    int n = sizeof(nums)/sizeof(nums[0]);
    int prefix[n][2];
    int zeros = 0, ones = 0;
    for (int i = 0; i < n; i++) {
        prefix[i][0] = zeros;
        prefix[i][1] = ones;
        if (nums[i] == 0) zeros++;
        else ones++;
    }
    int qsize = sizeof(queries)/sizeof(queries[0]);
    for (int i = 0; i < qsize; i++)
        cout << "\nquery " << i+1 << ": zeros = " << prefix[queries[i]][0] << ",ones =" << prefix[queries[i]][1];
    return 0;
}

আউটপুট

query 1: zeros = 1,ones =1
query 2: zeros = 2,ones =2
query 3: zeros = 0,ones =1
query 4: zeros = 0,ones =0
query 5: zeros = 2,ones =3

ব্যাখ্যা

• prefix[i] ইনডেক্স i-এর বামপাশের কাউন্ট রাখে (ইনডেক্স i নিজস্বই অন্তর্ভুক্ত নয়)।
• প্রিফিক্স বানানোর সময় প্রথমে কাউন্ট স্টোর করুন, তারপর বর্তমান এলিমেন্ট যোগ করুন।
• কোয়েরি টাইম: O(1)।

কমপ্লেক্সিটি