ஒரே சமமான மற்றும் ஒற்றைப்படை கூறுகளுடன் சுபரேக்களை எண்ணுங்கள்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அக்சன்சர் உண்மை வெறியர்கள்
அணி ஹாஷ்

நீங்கள் ஒரு முழு எண்ணைக் கொடுத்துள்ளீர்கள் என்று வைத்துக்கொள்வோம் வரிசை N அளவு. எண்கள் இருப்பதால், எண்கள் ஒற்றைப்படை அல்லது கூட. சிக்கல் அறிக்கை என்பது ஒரே சமமான மற்றும் ஒற்றைப்படை கூறுகளைக் கொண்ட எண்ணின் துணை வரிசை அல்லது சமமான மற்றும் ஒற்றைப்படை முழு எண்களைக் கொண்ட துணை வரிசைகளின் எண்ணிக்கையைக் கண்டறிகிறது.

உதாரணமாக

உள்ளீடு

arr [] = {2, 5, 1, 6};

வெளியீடு

3

விளக்கம்

⇒ {2, 5}, {1, 6}, {2, 5, 1, 6} இருப்பதால்

உள்ளீடு

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

வெளியீடு

7

அல்காரிதம்

  1. நேர்மறை + மற்றும் எதிர்மறை எண் n + 1 என்ற இரண்டு வரிசைகளை அறிவிக்கவும்.
  2. எண்ணிக்கை மற்றும் வெளியீட்டை 0 ஆக அமைக்கவும், நேர்மறை எண் [0] ஐ 1 ஆக அமைக்கவும்.
  3. வரிசையை கடந்து செல்லுங்கள் i = 0 முதல் i வரை
    1. பிட்வைஸ் மற்றும் செயல்பாடு arr [i] & 1 1 க்கு சமமாக இருக்கிறதா என்று சரிபார்க்கவும்,
      1. உண்மை என்றால், எண்ணிக்கையை 1 ஆல் அதிகரிக்கவும்.
    2. இல்லையெனில், எண்ணிக்கையை 1 குறைக்கவும்.
    3. எண்ணிக்கை 0 க்கும் குறைவாக இருந்தால், வெளியீட்டை எதிர்மறை எண் [-கவுண்ட்] இல் சேர்த்து வெளியீட்டில் சேமிக்கவும்.
    4. இல்லையெனில், வெளியீட்டை நேர்மறைநம் [எண்ணிக்கையில்] சேர்த்து வெளியீட்டில் சேமிக்கவும்.
  4. வெளியீடு திரும்பவும்.

விளக்கம்

இரண்டு ஹாஷ் வரிசைகளை உருவாக்குவோம், ஒன்று நேர்மறை வேறுபாட்டை சேமிப்பதற்காகவும், ஒன்று எதிர்மறை வேறுபாடுகளுக்காகவும். வேறுபாடுகளுடன், ஒற்றைப்படை மற்றும் முழு எண்களின் அதிர்வெண்களுக்கு இடையிலான வேறுபாடுகளை நாம் கண்டுபிடிக்கப் போகிறோம். வெளியீட்டை 0 ஆக அமைப்பது, இதில், எங்கள் பதிலை புதுப்பிப்போம், 0 ஆக எண்ணுவோம், இது வித்தியாச எண்ணிக்கையை பராமரிக்கும். இரண்டு ஹாஷ் வரிசைகளை அறிவித்த பிறகு, நேர்மறை ஒன்றை 1 ஆகவும், நேர்மறை எண் [0] = 1 ஆகவும் அமைக்கவும்.

நாங்கள் வரிசையை கடந்து செல்வோம், இது ஒற்றைப்படை மதிப்பு அல்லது நேர்மறை என்பதை சரிபார்க்கிறோம், இதற்காக நாங்கள் பிட்வைஸ் மற்றும் ஆபரேட்டரைப் பயன்படுத்துவோம், AND மற்றும் ஆபரேட்டரை 1 மற்றும் எந்த மதிப்பிற்கும் இடையில் பயன்படுத்தினால், இரண்டு முடிவுகளையும் 1 அல்லது 0 எனில் பெறுவோம் தி எண் ஒற்றைப்படை இது 1 ஐ ஒரு வெளியீடாகக் கொடுக்கும், அது அப்படியானால், அது 0 வெளியீடாகக் கொடுக்கும். எண் 1 எனக் கண்டறியப்பட்டால், நாம் எண்ணிக்கையை 1 ஆல் அதிகரிக்கப் போகிறோம், இல்லையெனில் அது 0 மட்டுமே முடியும், எனவே அதே எண்ணிக்கையின் மதிப்பை 1 ஆகக் குறைப்போம்.

இதைச் செய்யும்போது, ​​எங்கள் வெளியீட்டை நாம் பராமரிக்க வேண்டும், அதற்காக எண்ணிக்கையின் மதிப்பு 0 க்கும் குறைவாக இருப்பதைக் கண்டால், எதிர்மறை எண் எண்ணிக்கையின் குறியீட்டு மதிப்பின் வெளியீட்டை வெளியீட்டில் சேர்ப்போம், மேலும் எதிர்மறை எண்ணிக்கையை 1 ஆல் அதிகரிப்போம். 0 ஐ விட அதிகமாகவோ அல்லது சமமாகவோ உள்ள எண்ணை மட்டுமே நாங்கள் கண்டறிந்தோம், எனவே நேர்மறை எண்ணிக்கையின் குறியீட்டின் மதிப்புகளை வெளியீட்டில் சேர்ப்போம், மேலும் நேர்மறை எண்ணின் எண்ணிக்கையை 1 ஆல் அதிகரிப்போம். முக்கியமான விஷயம் என்னவென்றால், இரண்டின் ஒரே மதிப்பை நாம் காணும்போதெல்லாம் ஹாஷ் வரிசைகள் தற்போதைய குறியீடாகும், இதன் பொருள் எங்களுக்கு ஒரு ஒற்றைப்படை துணை வரிசையை கண்டுபிடித்தோம். கடைசியாக, வெளியீட்டை நாங்கள் திருப்பித் தருவோம்.

நடைமுறைப்படுத்தல்

ஒரே சமமான மற்றும் ஒற்றைப்படை கூறுகளைக் கொண்ட கவுண்ட் சுபரேக்களுக்கான சி ++ நிரல்

#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

ஒரே சமமான மற்றும் ஒற்றைப்படை கூறுகளைக் கொண்ட கவுண்ட் சுபரேக்களுக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (2 என்) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.