زیر مجموعه ها را با داشتن اعداد متمایز مجزا بشمارید


سطح دشواری ساده
اغلب در سیسکو Expedia میندا آزمایشگاههای SAP Taxi4Sure
صف مخلوط زیر مجموعه

همه ما در یک دوره یا در مصاحبه ای با مشکل زیرمجموعه دست و پنجه نرم کرده ایم. مصاحبه کنندگان نیز عاشق این مشکلات هستند. این مشکلات به آنها کمک می کند تا درک و همچنین روند فکر هر دانش آموز را بررسی کنند. بنابراین ، بدون هیچ زحمتی بیشتر ، اجازه دهید مستقیماً به مشکل بپردازیم.

بخش 1

بیانیه مسئله

اعداد ترکیبی / آرایشی به ما ارائه شده است. ما می خواهیم تعداد زیرمجموعه های خود را که دارای تعداد زوج منحصر به فرد است ، ثبت کنیم.

بگذارید یک مثال کوچک بزنیم:

ورودی:

[1,2,5,6,3,2,1,1,8]

زیر مجموعه های احتمالی:

[2,6]

[6,8]

[2,6,8]

توجه: زیرمجموعه هایی با شماره های مشابه متفاوت تلقی نخواهند شد

بگذارید با برجسته کردن یکی از زیر مجموعه های پاسخ احتمالی ، همین را نشان دهم.

زیر مجموعه ها را با داشتن اعداد متمایز مجزا بشمارید

بخش 2

تحلیل و بررسی

روشهای زیادی وجود دارد که می توانید بفهمید چه چیزی می خواهیم. نیروی بی رحم یکی از این موارد یافتن همه زیرمجموعه های ممکن و سپس یافتن مواردی است که قانون ما را برآورده می کنند.

روش فوق چیزی نیست که سر خود را به دیوار کوبید. بنابراین ، برای نجات شما از خجالت زدن احمقانه ، ساده ترین روش هایی را که می تواند به شما کمک کند در بهترین زمان ممکن به جواب برسید ، کار کرده ام.

هر بار که با یک عدد زوج روبرو می شویم ، دو انتخاب داریم

  • یا می تواند انتخاب کند که در زیرمجموعه باشد
  • این می تواند انتخاب کند که از زیرمجموعه خارج شود

بنابراین ، تنها وظیفه ای که اکنون با خود بر عهده داریم این است که مشخص کنیم تعداد منحصر به فرد است یا خیر. (با تشکر از قانون فوق الذکر)

اجازه دهید روند را صفر کنیم:

  • در مرحله اول ، حفظ HashSet برای ذخیره فروشگاهی از اعداد زوج که با آنها روبرو شده ایم
  • ثانیا ، یک حلقه را اجرا کنید
  • بررسی کنید که آیا یک عدد زوج است
  • اگر عدد زوج باشد HashSet را به آن اضافه می کنیم
  • HashSet دارای نظم شخصی است که اطمینان می دهد ما فقط عناصر منحصر به فرد را در اختیار داریم
  • سپس تعداد عناصر را در HashSet می یابیم
  • این تعداد نشانگر تعداد زوج های منحصر به فرد ما است
  • می توانیم با استفاده از این تعداد تعداد زیر مجموعه ها را پیدا کنیم
  • تعداد زیرمجموعه ها = 2 ^ تعداد 1

فرایند بالا را می توان به صورت کدگذاری کرد:

کد جاوا برای زیر مجموعه های دارای تعداد زوج مجزا

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

کد ++ C برای زیر مجموعه های دارای تعداد زوج مجزا

همانطور که از Java به C ++ تغییر می دهیم از Unordered Set به جای HashSet استفاده خواهیم کرد و چند پارامتر را متناسب با ما دور می زنیم.

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

تجزیه و تحلیل پیچیدگی برای زیر مجموعه های تعداد دارای زوج مجزا

پیچیدگی زمان = O (n)

پیچیدگی فضا = O (n)

پیچیدگی زمان

  • وقتی از آرایه عبور می کنیم O (n) است
  • ما قبل از افزودن هر عنصر به زیرمجموعه ، هر یک از آنها را بررسی می کنیم

پیچیدگی فضا

  • O (n) است زیرا در بدترین حالت ممکن است کل آرایه را ذخیره کنیم