સમાન સમાન અને વિચિત્ર તત્વો સાથે સુબેર્રેઝની ગણતરી કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર ફેક્ટસેટ કટ્ટરતા
અરે હેશ

ધારો કે તમે પૂર્ણાંક આપ્યો છે એરે એન કદ. જેમ કે સંખ્યાઓ છે, સંખ્યાઓ વિચિત્ર અથવા સમાન છે. સમસ્યાનું નિવેદન સમાન અને વિચિત્ર તત્વો સાથે સબઅરેરે ગણાય છે અથવા સમાન અને વિચિત્ર પૂર્ણાંકોની સમાન સંખ્યા ધરાવતા પેટા-એરેની ગણતરી શોધી કા .ે છે.

ઉદાહરણ

ઇનપુટ

એઆર [] = {2, 5, 1, 6};

આઉટપુટ

3

સમજૂતી

જેમ કે ત્યાં ⇒ {2, 5}, {1, 6}, {2, 5, 1, 6}

ઇનપુટ

એરે [] = {2,3,4,5,1,6}

આઉટપુટ

7

અલ્ગોરિધમ

  1. બે એરે, પોઝિટિવનમ અને નેગેટિવમ કદ +1 XNUMX જાહેર કરો.
  2. ગણતરી અને આઉટપુટ 0 પર સેટ કરો, અને સકારાત્મકમ [0] થી 1 સેટ કરો.
  3. એરેને પસાર કરો i = 0 થી, i
    1. બિટવાઇઝ અને ઓપરેશન એરે [i] અને 1 બરાબર 1 છે કે નહીં તે તપાસો
      1. જો સાચું છે, તો પછી ગણતરી 1 દ્વારા વધારો.
    2. બાકી, ગણતરી 1 દ્વારા ઘટાડો.
    3. જો ગણતરી 0 કરતા ઓછી હોય, તો આઉટપુટ નેગેટિવમ [-કાઉન્ટ] માં ઉમેરો અને આઉટપુટમાં સ્ટોર કરો.
    4. બાકી, આઉટપુટને પોઝિટિવમ [ગણતરી] પર ઉમેરો અને આઉટપુટમાં સ્ટોર કરો.
  4. રીટર્ન આઉટપુટ.

સમજૂતી

અમે બે હેશ એરે બનાવીશું, એક સકારાત્મક તફાવત સંગ્રહવા માટે, અને એક નકારાત્મક તફાવતો માટે. મતભેદો સાથે, અમારું કહેવું છે કે, આપણે વિચિત્ર અને પૂર્ણાંકોની આવર્તન વચ્ચેના તફાવતો શોધીશું. આઉટપુટ 0 ઉપર સુયોજિત કરીશું, આમાં, આપણે આપણું જવાબ અપડેટ કરીશું, 0 ને ગણતરી કરીશું, આ તફાવતની ગણતરી જાળવશે. બે હેશ એરે જાહેર કર્યા પછી, સકારાત્મક એક થી 1 સેટ કરો, સકારાત્મક 0 [1] = XNUMX.

આપણે એરેને પસાર કરીશું, અને તપાસ કરીશું કે તે કોઈ વિચિત્ર મૂલ્ય છે કે સકારાત્મક છે, આ માટે આપણે બીટવાઇઝ અને operatorપરેટરનો ઉપયોગ કરીશું, જો 1 અને કોઈ પણ મૂલ્ય વચ્ચેના ઓ.ડી. આ સંખ્યા વિચિત્ર છે તે આઉટપુટ તરીકે 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 એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.