এক অ্যারে অন্য অ্যারের সাবসেট কিনা যাচাই করা

সমস্যা বিবরণ

দুটি অ্যারে arr1[] এবং arr2[] দেওয়া হয়েছে, যাদের আকার যথাক্রমে m এবং n। উভয় অ্যারে অসাজানো এবং স্বতন্ত্র উপাদান রয়েছে। আমাদের কাজ হল arr2 কি arr1-এর সাবসেট কিনা তা যাচাই করা।

উদাহরণ

ইনপুট: arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1}
আউটপুট: arr2, arr1-এর সাবসেট।

পদ্ধতি ১: নেস্টেড লুপ (O(m×n))

arr2-এর প্রতিটি উপাদান arr1-এ খুঁজে বের করা।

#include <iostream>
using namespace std;

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < m; j++)
            if (arr2[i] == arr1[j]) break;
        if (j == m) return false;
    }
    return true;
}

পদ্ধতি ২: সর্টিং + বাইনারি সার্চ (O(m log m + n log m))

arr1 সর্ট করে arr2-এর প্রতিটি উপাদান বাইনারি সার্চ দিয়ে খুঁজা।

পদ্ধতি ৩: উভয় অ্যারে সর্ট করে টু-পয়েন্টার (O(m log m + n log n))

দুই অ্যারে সর্ট করে পয়েন্টার তুলনা করে সাবসেট যাচাই।

পদ্ধতি ৪: হ্যাশিং (O(m + n))

arr1-এর উপাদানগুলো হ্যাশ সেটে রাখে arr2-এর উপাদান খুঁজা।

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

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    unordered_set<int> s;
    for (int i = 0; i < m; i++) s.insert(arr1[i]);
    for (int i = 0; i < n; i++)
        if (s.find(arr2[i]) == s.end()) return false;
    return true;
}

পদ্ধতি ৫: সেট ডেটা স্ট্রাকচার (O(m + n))

arr1 দিয়ে সেট বানিয়ে arr2 ইনসার্ট করলে সাইজ বাড়লে সাবসেট নয়।

আউটপুট (সকল পদ্ধতির জন্য)

arr2[] is subset of arr1[]

এক অ্যারে অন্য অ্যারের সাবসেট কিনা যাচাই করা - ৫টি পদ্ধতি (C++)