এই সমস্যায়, আমাদেরকে m এবং n আকারের arr1[] এবং arr2[] পূর্ণসংখ্যার দুটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল একটি অ্যারে অন্য অ্যারের উপসেট কিনা তা খুঁজে বের করা - যোগ করা পদ্ধতি 3 .
উভয় অ্যারে arr1[] এবং arr2[] unorder এবং আলাদা উপাদান আছে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1}
Output : arr2 is a subset of arr1. সমাধান পদ্ধতি
এই সমস্যা সমাধানের জন্য, আমরা এখানে একাধিক পদ্ধতি নিয়ে আলোচনা করেছি। আসুন একটি প্রোগ্রাম সহ তাদের প্রত্যেকের কাজ দেখি।
পদ্ধতি 1
সমস্যা সমাধানের একটি পদ্ধতি হল সরাসরি উপসেট পরীক্ষা করা। এটি অ্যারে অ্যারের প্রতিটি উপাদানের জন্য বাইরের এবং ভিতরের একটি, অ্যারের অ্যারের প্রতিটি উপাদানের জন্য নেস্টেড লুপ ব্যবহার করে করা হয়। আমরা পরীক্ষা করব arr2-এর প্রতিটি উপাদান arr1-এ উপস্থিত আছে কিনা, যদি এটি 1 রিটার্ন হয় ( arr2 হল arr1-এর সাবয়ারে) অন্যথায় 0 ফেরত দিন (arr2 arr1-এর সাবয়ারে নয়)।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
int j = 0;
for (int i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (arr2[i] == arr1[j])
break;
}
if (j == m)
return false;
}
return true;
}
int main(){
int arr1[] = {5, 2, 1, 6, 8, 10};
int arr2[] = {6, 2, 1};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
return 0;
} আউটপুট
arr2[] is subset of arr1[]
পদ্ধতি 2
সমস্যা সমাধানের আরেকটি পদ্ধতি হল arr1-এ arr2-এর সমস্ত উপাদান আছে কিনা তা পরীক্ষা করা। এটি কার্যকরভাবে করার জন্য, আমরা অ্যারে arr1[] সাজিয়ে দেব এবং তারপর arr2-এর প্রতিটি উপাদানের জন্য, arr1[]-এ arr2[]-এর উপাদানগুলি অনুসন্ধান করতে বাইনারি অনুসন্ধান করুন। এখন, যদি কোনো এলিমেন্ট না পাওয়া যায়, রিটার্ন 0 (arr2 arr1-এর subarray নয়) এবং arr2-এর সমস্ত উপাদান arr1-এ উপস্থিত থাকলে, রিটার্ন 1 (arr2 হল arr1-এর একটি সাবয়ারে)।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high, int x){
if (high >= low){
int mid = (low + high) / 2;
if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid - 1), x);
}
return -1;
}
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
int i = 0;
sort(arr1, arr1 + m);
for (i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
return 0;
}
return 1;
}
int main(){
int arr1[] = {5, 2, 1, 6, 8, 10};
int arr2[] = {6, 2, 1};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
return 0;
} আউটপুট
arr2[] is subset of arr1[]
পদ্ধতি 3
সমাধান খুঁজে বের করার আরেকটি পদ্ধতি হল প্রথমে অ্যারে 1[] এবং arr2[] উভয় অ্যারে সাজানো। তারপর অ্যারের সমস্ত উপাদানের জন্য arr2[] তারা arr1[] এ উপস্থিত আছে কিনা তা পরীক্ষা করুন। এর জন্য, আমাদের কাছে একটি সরল পদ্ধতি রয়েছে যা উভয় অ্যারেতে উপাদানের সূচী ব্যবহার করছে।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
int i = 0, j = 0;
if (m < n)
return 0;
sort(arr1, arr1 + m);
sort(arr2, arr2 + n);
while (i < n && j < m){
if (arr1[j] < arr2[i])
j++;
else if (arr1[j] == arr2[i]){
j++;
i++;
}
else if (arr1[j] > arr2[i])
return 0;
}
return (i < n) ? false : true;
}
int main()
{
int arr1[] = {5, 2, 1, 6, 8, 10};
int arr2[] = {6, 2, 1};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
return 0;
} আউটপুট
arr2[] is subset of arr1[]
পদ্ধতি 4
আরও একটি পদ্ধতি, arr2 arr1 এর উপসেট কিনা তা পরীক্ষা করার জন্য হ্যাশিং ব্যবহার করছে . আমরা arr1 এর সমস্ত উপাদান ব্যবহার করে একটি হ্যাশ টেবিল তৈরি করব এবং তারপর হ্যাশ টেবিলে arr2 এর উপাদানগুলি অনুসন্ধান করব। যদি মানগুলি পাওয়া যায়, তাহলে 1 ফেরত দিন (arr2 হল arr1-এর একটি উপসেট) অন্যথায় 0 ফেরত দিন (arr2 arr1-এর উপসেট নয়)।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
set<int> arr1Hash;
for (int i = 0; i < m; i++)
arr1Hash.insert(arr1[i]);
for (int i = 0; i < n; i++) {
if (arr1Hash.find(arr2[i]) == arr1Hash.end())
return false;
}
return true;
}
int main(){
int arr1[] = {5, 2, 1, 6, 8, 10};
int arr2[] = {6, 2, 1};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
return 0;
} আউটপুট
arr2[] is subset of arr1[]
পদ্ধতি 5
সমস্যা সমাধানের আরেকটি পদ্ধতি হল সেট ডেটা স্ট্রাকচার ব্যবহার করা . আমরা arr1 এর সমস্ত মান সহ একটি নতুন সেট তৈরি করব এবং এর দৈর্ঘ্য পরীক্ষা করব। তারপরে আমরা arr2 এর সমস্ত মান সন্নিবেশ করার চেষ্টা করব, যদি যোগ করলে দৈর্ঘ্য পরিবর্তন হয় তবে arr2 arr1 এর উপসেট নয়। যদি arr2-এর উপাদান যোগ করার পর দৈর্ঘ্যের কোন পরিবর্তন না হয় তাহলে arr2 হল arr1-এর উপসেট।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
unordered_set<int> arrSet;
for (int i = 0; i < m; i++) {
arrSet.insert(arr1[i]);
}
int setSize = arrSet.size();
for (int i = 0; i < n; i++) {
arrSet.insert(arr2[i]);
}
if (arrSet.size() == setSize) {
return true;
}
else {
return false;
}
}
int main(){
int arr1[] = {5, 2, 1, 6, 8, 10};
int arr2[] = {6, 2, 1};
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
return 0;
} আউটপুট
arr2[] is subset of arr1[]
