ഒരേ തുല്യവും വിചിത്രവുമായ ഘടകങ്ങൾ ഉപയോഗിച്ച് സബ്‌റേകൾ എണ്ണുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് ഫാക്റ്റ്സെറ്റ് ഫനാറ്റിക്സ്
അറേ ഹാഷ്

നിങ്ങൾ ഒരു സംഖ്യ നൽകിയിട്ടുണ്ടെന്ന് കരുതുക ശ്രേണി 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. എണ്ണവും output ട്ട്‌പുട്ടും 0 ആയി സജ്ജമാക്കുക, കൂടാതെ പോസിറ്റീവ് നം [0] 1 ആയി സജ്ജമാക്കുക.
  3. അറേയിലൂടെ സഞ്ചരിക്കുക i = 0 മുതൽ i വരെ
    1. ബിറ്റ്‌വൈസും പ്രവർത്തനവും [i] & 1 1 ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക,
      1. ശരിയാണെങ്കിൽ, എണ്ണം 1 വർദ്ധിപ്പിക്കുക.
    2. അല്ലെങ്കിൽ, എണ്ണം 1 കുറയ്ക്കുക.
    3. എണ്ണം 0-ൽ കുറവാണെങ്കിൽ, negative ട്ട്‌പുട്ട് നെഗറ്റീവ്നൂമിലേക്ക് [-ക ount ണ്ട്] ചേർത്ത് .ട്ട്‌പുട്ടിൽ സംഭരിക്കുക.
    4. അല്ലെങ്കിൽ, positive ട്ട്‌പുട്ട് പോസിറ്റീവ്നൂമിലേക്ക് ചേർത്ത് [എണ്ണം] അതിനെ .ട്ട്‌പുട്ടിൽ സംഭരിക്കുക.
  4. Return ട്ട്‌പുട്ട് നൽകുന്നു.

വിശദീകരണം

ഞങ്ങൾ രണ്ട് ഹാഷ് അറേകളാക്കും, ഒന്ന് പോസിറ്റീവ് വ്യത്യാസം സംഭരിക്കുന്നതിന്, ഒന്ന് നെഗറ്റീവ് വ്യത്യാസങ്ങൾക്ക്. വ്യത്യാസങ്ങൾക്കൊപ്പം, വിചിത്രമായതും പൂർണ്ണസംഖ്യകളുടെതുമായ ആവൃത്തികൾ തമ്മിലുള്ള വ്യത്യാസങ്ങൾ കണ്ടെത്താൻ ഞങ്ങൾ പോകുന്നു. 0 ട്ട്‌പുട്ട് 0 ആയി സജ്ജമാക്കുന്നു, ഇതിൽ, ഞങ്ങൾ ഉത്തരം അപ്‌ഡേറ്റുചെയ്യും, 1 ആയി എണ്ണുക, ഇത് വ്യത്യാസങ്ങളുടെ എണ്ണം നിലനിർത്തും. രണ്ട് ഹാഷ് അറേകൾ പ്രഖ്യാപിച്ചതിന് ശേഷം, പോസിറ്റീവ് ഒന്ന് 0, പോസിറ്റീവ്നൂം [1] = XNUMX എന്നിങ്ങനെ സജ്ജമാക്കുക.

ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കും, അത് വിചിത്രമായ മൂല്യമാണോ പോസിറ്റീവ് ആണോ എന്ന് പരിശോധിക്കും, ഇതിനായി ഞങ്ങൾ ബിറ്റ്വൈസ് ആന്റ് ഓപ്പറേറ്റർ ഉപയോഗിക്കും, AND നും ഓപ്പറേറ്ററിനും 1 നും ഏതെങ്കിലും മൂല്യത്തിനും ഇടയിൽ ഉപയോഗിക്കുകയാണെങ്കിൽ, രണ്ട് ഫലവും നമുക്ക് ലഭിക്കും, 1 അല്ലെങ്കിൽ 0, ദി നമ്പർ വിചിത്രമാണ് അത് 1 output ട്ട്‌പുട്ടായി നൽകും, അങ്ങനെയാണെങ്കിൽപ്പോലും, അത് 0 ട്ട്‌പുട്ടായി 1 നൽകുന്നു. സംഖ്യ 1 ആണെന്ന് കണ്ടെത്തിയാൽ, ഞങ്ങൾ എണ്ണം 0 വർദ്ധിപ്പിക്കാൻ പോകുന്നു, അല്ലാത്തപക്ഷം 1 മാത്രമേ ചെയ്യാനാകൂ, അതിനാൽ അതേ എണ്ണം മൂല്യം XNUMX കുറയ്ക്കും.

ഇത് ചെയ്യുമ്പോൾ, ഞങ്ങളുടെ output ട്ട്പുട്ട് ഞങ്ങൾ നിലനിർത്തണം, അതിനായി എണ്ണത്തിന്റെ മൂല്യം 0 ൽ കുറവാണെന്ന് ഞങ്ങൾ കണ്ടെത്തിയാൽ, നെഗറ്റീവ്നൂം എണ്ണത്തിന്റെ സൂചിക മൂല്യത്തിന്റെ output ട്ട്‌പുട്ടിലേക്ക് ഞങ്ങൾ ചേർക്കുകയും നെഗറ്റീവ്നൂമിന്റെ എണ്ണം 1 വർദ്ധിപ്പിക്കുകയും ചെയ്യും. 0 എന്നതിനേക്കാൾ വലുതോ തുല്യമോ ആയ സംഖ്യ മാത്രമേ ഞങ്ങൾ കണ്ടെത്തിയിട്ടുള്ളൂ, അതിനാൽ ഞങ്ങൾ പോസിറ്റീവ് നം എണ്ണത്തിന്റെ സൂചികയുടെ മൂല്യങ്ങൾ output ട്ട്‌പുട്ടിലേക്ക് ചേർക്കുകയും പോസിറ്റീവ്നൂമിന്റെ എണ്ണം 1 വർദ്ധിപ്പിക്കുകയും ചെയ്യും. പ്രധാന കാര്യം, രണ്ടിന്റെയും ഒരേ മൂല്യം കണ്ടെത്തുമ്പോഴെല്ലാം ഹാഷ് അറേകളുടെ നിലവിലെ സൂചിക, അതിനർ‌ത്ഥം ഞങ്ങൾ‌ക്കായി ഒരു വിചിത്രമായ ഉപ-അറേ കണ്ടെത്തി. അവസാനം, ഞങ്ങൾ return ട്ട്‌പുട്ട് നൽകും.

നടപ്പിലാക്കൽ

ഒരേ തുല്യവും വിചിത്രവുമായ ഘടകങ്ങൾ ഉള്ള കൗണ്ട് സബ്‌റേകൾക്കായുള്ള സി ++ പ്രോഗ്രാം

#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

ഒരേ തുല്യവും വിചിത്രവുമായ ഘടകങ്ങൾ ഉള്ള കൗണ്ട് സബ്‌റേകൾക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (2n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.