একই সমান এবং বিজোড় উপাদানগুলির সাথে সাববারেগুলি গণনা করুন  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় Accenture ফ্যাক্সেট ধর্মান্ধদের
বিন্যাস কাটা

মনে করুন আপনি একটি পূর্ণসংখ্যা দিয়েছেন বিন্যাস এন আকারের। সংখ্যা যেমন আছে, সংখ্যাগুলি বিজোড় বা এমনকি সমান। সমস্যা বিবৃতিটি সমান এবং বিজোড় উপাদানগুলির সাথে সাববারে গণনা করা হয় বা সম-সংখ্যক সমান এবং বিজোড় পূর্ণসংখ্যার সাব-অ্যারেগুলির গণনা বের করে।

উদাহরণ  

ইনপুট

আরআর [] = {2, 5, 1, 6};

আউটপুট

3

ব্যাখ্যা

যেমন ⇒ {2, 5}, {1, 6}, {2, 5, 1, 6

ইনপুট

আরআর [] = {2,3,4,5,1,6}

আউটপুট

7

অ্যালগরিদম  

  1. দুটি অ্যারে, পজিটিভনাম এবং নেগেটিভনাম আকারের এন + 1 ঘোষণা করুন।
  2. গণনা এবং আউটপুট 0 তে সেট করুন এবং ইতিবাচক সংখ্যা [0] থেকে 1 এ সেট করুন।
  3. অ্যারে অতিক্রম করুন i = 0 থেকে i
    1. বিটওয়াইজ এবং অপারেশন অ্যারে [i] এবং 1 সমান 1,
      1. যদি সত্য হয়, তবে গণনাটি 1 দ্বারা বাড়ান।
    2. অন্যথায়, গণনাটি 1 দ্বারা হ্রাস করুন।
    3. যদি গণনা 0 এর চেয়ে কম হয় তবে আউটপুটটিকে নেগেটিভনাম [-count] এ যুক্ত করুন এবং আউটপুটে সংরক্ষণ করুন।
    4. অন্যথায়, আউটপুটটিকে পজিটিভনাম [গণনা] এ যুক্ত করুন এবং আউটপুট এ সঞ্চয় করুন।
  4. রিটার্ন আউটপুট।

ব্যাখ্যা  

আমরা দুটি হ্যাশ অ্যারে করব, একটি ইতিবাচক পার্থক্য সংরক্ষণ করার জন্য, এবং একটি নেতিবাচক পার্থক্যের জন্য। পার্থক্য সহ, আমরা বলতে চাই, আমরা বিজোড় এবং এমনকি পূর্ণসংখ্যার ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্যগুলি সন্ধান করতে যাচ্ছি। আউটপুট 0 এ সেট করা, এটিতে আমরা আমাদের উত্তর আপডেট করব, 0 গণনা করব, এটি পার্থক্য গণনা বজায় রাখবে। দুটি হ্যাশ অ্যারে ঘোষণার পরে ধনাত্মককে 1 তে 0, ধনাত্মকনাম [1] = XNUMX সেট করুন।

আরো দেখুন
উচ্চতার মধ্যে সর্বোচ্চ পার্থক্য হ্রাস করুন

আমরা অ্যারেটি অতিক্রম করব এবং এটি পরীক্ষা করে দেখব যে এটি কোনও বিজোড় মান বা ধনাত্মক কিনা, এর জন্য আমরা বিটওয়াইস এবং অপারেটর ব্যবহার করব, যদি 1 ও কোনও মানের মধ্যে অ্যান্ড অপারেটর ব্যবহার করি তবে আমরা দুটি ফলাফল পাব, হয় 1 বা 0, যদি হয় দ্য সংখ্যাটি বিজোড় এটি আউটপুট হিসাবে 1 দেবে, এমনকি যদি এটি হয় তবে এটি 0 আউটপুট হিসাবে দেয়। যদি সংখ্যাটি 1 হিসাবে পাওয়া যায় তবে আমরা গণনাটি 1 দ্বারা বাড়িয়ে যাচ্ছি, অন্যথায় এটি কেবল 0 টি করতে পারে, সুতরাং আমরা একই গণনা মান 1 দ্বারা হ্রাস করব।

এটি করার সময়, আমাদের আমাদের আউটপুট বজায় রাখা উচিত, এর জন্য যদি আমরা খুঁজে পেয়েছি যে গণনার মান 0 এর চেয়ে কম হয়, তবে আমরা আউটপুটে নেতিবাচক নম্বরের গণনার সূচকের মান যুক্ত করব এবং নেতিবাচক সংখ্যা 1 দ্বারা বাড়িয়ে দেব se আমরা কেবল 0 এর চেয়ে বড় বা সমান সংখ্যাটি পেয়েছি, সুতরাং আমরা আউটপুটে ধনাত্মক সংখ্যা গণনা সূচকের মানগুলি যুক্ত করব এবং ইতিবাচক সংখ্যাটি 1 দিয়ে বাড়িয়ে দেব XNUMX গুরুত্বপূর্ণ বিষয়টি যখনই আমরা উভয়ের উভয়ের সমান মান খুঁজে পাই হ্যাশ বর্তমান সূচকের অ্যারে করে, এর অর্থ আমরা আমাদের জন্য একটি সম-বিভেদ উপ-অ্যারে পেয়েছি। এবং শেষ পর্যন্ত, আমরা আউটপুট ফিরে আসব।

বাস্তবায়ন  

একই ইওন এবং বিজোড় উপাদানগুলির সাথে গণনা সাববারির জন্য সি ++ প্রোগ্রাম

#include<iostream>
#include<unordered_map>

using namespace std;

int getOESubarrays(int arr[], int n)
{
    int count = 0;
    int output = 0;

    int positiveNum[n+1];
    int negativeNum[n+1];

    positiveNum[0] = 1;

    for (int i = 0; i < n; i++)
    {
        if ((arr[i] & 1) == 1) count++;
        else count--;

        if (count < 0)
        {
            output += negativeNum[-count];
            negativeNum[-count]++;
        }
        else
        {
            output += positiveNum[count];
            positiveNum[count]++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2,3,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Even Odd Sub-Arrays are: " << getOESubarrays(arr,n);
    return 0;
}
Even Odd Sub-Arrays are: 7

একই সমান এবং বিজোড় উপাদানগুলির সাথে গণনা সাববারির জন্য জাভা প্রোগ্রাম

class oddEvenSubArrays
{
    public static int getOESubarrays(int[] arr, int n)
    {
        int count = 0;
        int output = 0;

        int positiveNum[] = new int[n + 1];
        int negativeNum[] = new int[n + 1];

        positiveNum[0] = 1;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) == 1) count++;
            else count--;

            if (count < 0)
            {
                output += negativeNum[-count];
                negativeNum[-count]++;
            }
            else
            {
                output += positiveNum[count];
                positiveNum[count]++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,4,5,1,6};
        int n = arr.length;
        System.out.println("Even Odd Sub-Arrays are: "+getOESubarrays(arr, n));
    }
}
Even Odd Sub-Arrays are: 7

একই সমান এবং বিজোড় উপাদানগুলির সাথে গণনা সাববারির জন্য জটিলতা বিশ্লেষণ  

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

আরো দেখুন
কে দ্বারা যোগ বিভাজনের সাথে যুক্তগুলিতে অ্যারে বিভক্ত করা হচ্ছে

স্পেস জটিলতা ity

ও (2 এন) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।