Преброј подређаје са истим парним и непарним елементима


Ниво тешкоће Лако
Често питани у Аццентуре Фацтсет Фанатици
Ред Хасх

Претпоставимо да сте дали цео број поредак величине Н. Како постоје бројеви, бројеви су непарни или парни. Изјава о проблему је броји подниз с истим парним и непарним елементима или сазнаје број под низа који има једнак број парних и непарних целих бројева.

Пример

Улазни

арр [] = {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. Пређите низ од и = 0, до и
    1. Проверите да ли је битни и рад арр [и] & 1 једнак 1,
      1. Ако је тачно, повећајте број за 1.
    2. У супротном, смањите број за 1.
    3. Ако је бројање мање од 0, додајте излаз у негативни број [-број] и спремите га у излаз.
    4. Иначе, додајте излаз у поситивеНум [цоунт] и похраните га у излаз.
  4. Повратни излаз.

Објашњење

Направићемо два хеш-низа, један за чување позитивне разлике, а други за негативне разлике. Са разликама, мислимо рећи, сазнаћемо разлике између фреквенција непарних и парних целих бројева. Постављањем излаза на 0, у овом ћемо ажурирати наш одговор, бројати на 0, ово ће задржати број разлика. Након декларисања два хеш поља, поставите позитивну на 1, поситивеНум [0] = 1.

Прећи ћемо низ, и проверити да ли је непарна или позитивна вредност, за то ћемо користити битни АНД оператор, ако користимо АНД оператор између 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

Анализа сложености за подбројеве броја са истим парним и непарним елементима

Сложеност времена

Он) где „Н“ је број елемената у низу.

Сложеност простора

О (2н) где „Н“ је број елемената у низу.