এই সমস্যায়, আমাদের Q কোয়েরি দেওয়া আছে। এগুলো তিন টাইপের, সেগুলো হল -
কোয়েরি ১: লিস্টে সংখ্যা N যোগ করা।
কোয়েরি ২: লিস্ট থেকে সংখ্যা N মুছে ফেলা।
কোয়েরি ৩: লিস্টের সর্বোচ্চ এবং ন্যূনতম উপাদানের পার্থক্য ফেরত দেওয়া।
আমাদের কাজ হল কোয়েরি যোগ, মুছে ফেলা, এবং সর্বোচ্চ-ন্যূনতম পার্থক্য ফেরত দেওয়া সমাধান করার প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমাদের Q সংখ্যক কোয়েরি দেওয়া থাকবে যা লিস্টে করা হবে। ৩ টাইপের কোয়েরি আছে যোগ, মুছে ফেলা, এবং সর্বোচ্চ ও ন্যূনতম উপাদানের পার্থক্য বের করা। যেসব কোয়েরি ব্যবহার করে আমরা প্রথমে এলিমেন্টের লিস্ট তৈরি করব এবং তারপর কোয়েরি ৩-এর মান অর্থাৎ সর্বোচ্চ এবং ন্যূনতম এলিমেন্টের পার্থক্য বের করব।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: Q = 6
Query (1, 4)
Query (1, 9)
Query (1, 6)
Query (2, 4)
Query (1, 3)
Query (3)
আউটপুট: 6
ব্যাখ্যা
শেষে লিস্টটি হবে {9, 6, 3}।
সর্বোচ্চ -> 9
ন্যূনতম -> 3
পার্থক্য -> 6
সমাধান পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল প্রতিটি কোয়েরি সরাসরি সমাধান করা। নিচের ধাপগুলো অনুসরণ করে -
একটি অ্যারে আরম্ভ করুন।
কোয়েরি টাইপ ১ এর জন্য, অ্যারেতে এলিমেন্ট যোগ করুন।
কোয়েরি টাইপ ২ এর জন্য, অ্যারে থেকে এলিমেন্ট মুছে ফেলুন।
কোয়েরি টাইপ ৩ এর জন্য, সর্বোচ্চ ও ন্যূনতমের পার্থক্য বের করুন এবং ফেরত দিন।
C++ প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)
#include <iostream>
using namespace std;
void solveQuerry(int type, int item){
int list[100];
static int index = 0;
if(type == 1){
list[index] = item;
index++;
}
else if(type == 2){
for(int i = 0; i <= index; i++)
if(list[i] == item ){
list[i] = 0;
break;
}
}
else if(type == 3){
int max = -100, min = 100;
for(int i = 0; i< index; i++){
if(list[i] == 0)
i++;
if(list[i] > max)
max = list[i];
if(list[i] < min)
min = list[i];
}
cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
}
}
int main() {
int Q = 6;
int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
for(int i = 0; i< Q; i++){
solveQuerry(query[i][0], query[i][1]);
}
}
আউটপুট
The difference between the maximum and minimum elements of the list is 6
সার্চ প্রসেস আরও দক্ষ করা যায় যদি সিম্পল অ্যারে না ব্যবহার করে অন্যান্য ডেটা স্ট্রাকচার ব্যবহার করা হয়। এখানে, যদি আমরা সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি ব্যবহার করি অ্যারে বদলে। তবে ম্যাক্স এলিমেন্ট শেষে থাকবে (rbegin() মেথড দিয়ে এক্সেসIBLE)। এবং মিন এলিমেন্ট শুরুতে থাকবে (begin() মেথড দিয়ে এক্সেসIBLE)।
C++-এ সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রির ইমপ্লিমেন্টেশন সেট (set) দিয়ে করা হয়।
C++ প্রোগ্রাম উদাহরণ (Set ব্যবহার করে দক্ষ পদ্ধতি)
#include <bits/stdc++.h>
using namespace std;
set<int> myList;
void solveQuerry(int type, int num){
if(type == 1){
myList.insert(num);
}
else if(type == 2){
myList.erase(num);
}
else if(type == 3){
int max = *(myList.rbegin());
int min = *(myList.begin());
cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
}
}
int main() {
int Q = 6;
int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
for(int i = 0; i< Q; i++){
solveQuerry(query[i][0], query[i][1]);
}
}
আউটপুট
The difference between the maximum and minimum elements of the list is 6
