එකම ඒකාකාර හා නොගැලපෙන මූලද්‍රව්‍ය සහිත සබ්බ්‍රේ ගණන් කරන්න  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇක්සෙන්චර් ෆැක්ට්සෙට් උන්මත්තකයෝ
අරා හැෂ්

ඔබ පූර්ණ සංඛ්‍යාවක් ලබා දී ඇතැයි සිතමු අරාව 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 ප්‍රමාණයේ ධන ධන හා negative ණ සංඛ්‍යා අරා දෙකක් ප්‍රකාශ කරන්න.
  2. ගණන් කිරීම සහ ප්‍රතිදානය 0 ලෙස සකසා ධන සංඛ්‍යා [0] 1 ට සකසන්න.
  3. අරාව හරහා ගමන් කරන්න i = 0 සිට i දක්වා
    1. බිට්වේස් සහ ක්‍රියාකාරිත්වය අර [i] සහ 1 1 ට සමාන දැයි පරීක්ෂා කරන්න,
      1. සත්‍ය නම්, ගණන 1 කින් වැඩි කරන්න.
    2. නැතහොත්, ගණන 1 කින් අඩු කරන්න.
    3. ගණන් කිරීම 0 ට වඩා අඩු නම්, ප්‍රතිදානය negative ණ අංක [-කවුන්ට්] වෙත එකතු කර ප්‍රතිදානයට ගබඩා කරන්න.
    4. නැතහොත්, ප්‍රතිදානය ධනාත්මක අංකයට එකතු කර [ප්‍රති] ලයට ගබඩා කරන්න.
  4. ප්‍රතිදානය නැවත ලබා දෙන්න.

පැහැදිලි කිරීම  

අපි හැෂ් අරා දෙක සාදන්නෙමු, එකක් ධනාත්මක වෙනස ගබඩා කිරීම සඳහා වන අතර එකක් negative ණාත්මක වෙනස්කම් සඳහා ය. වෙනස්කම් සමඟ, අපි කියන්නට අදහස් කරන්නේ, අපි අමුතු සංඛ්‍යා හා සංඛ්‍යා සංඛ්‍යා අතර වෙනස්කම් සොයා ගැනීමට යන බවයි. ප්‍රතිදානය 0 ට සැකසීම, මෙහි දී අපි අපගේ පිළිතුර යාවත්කාලීන කරන්නෙමු, 0 ට ගණන් කරන්න, මෙය වෙනස ගණනය කරයි. හැෂ් අරා දෙකක් ප්‍රකාශයට පත් කිරීමෙන් පසු, ධනාත්මක එක 1 ට, ධන සංඛ්‍යා [0] = 1 ලෙස සකසන්න.

මෙයද බලන්න
උස අතර උපරිම වෙනස අවම කරන්න

අපි අරාව හරහා ගමන් කර එය අමුතු අගයක් හෝ ධනාත්මක දැයි පරික්ෂා කරන්නෙමු, මේ සඳහා අපි බිට්වයිස් සහ ක්‍රියාකරු භාවිතා කරන්නෙමු, AND ක්‍රියාකරු 1 සහ ඕනෑම අගයක් අතර භාවිතා කරන්නේ නම්, අපට ප්‍රති result ල දෙක ලැබෙනු ඇත, 1 හෝ 0, එම අංකය අමුතුයි එය ප්‍රතිදානයක් ලෙස 1 ක් ලබා දෙනු ඇත, එය එසේ වුවහොත් එය ප්‍රතිදානයක් ලෙස 0 ලබා දෙයි. අංකය 1 බව සොයාගත හොත්, අපි ගණන් කිරීම 1 කින් වැඩි කරන්නෙමු, නැතිනම් එය 0 ක් පමණක් කළ හැකිය, එබැවින් අපි එකම ගණන් කිරීමේ අගය 1 කින් අඩු කරන්නෙමු.

මෙය සිදු කරන අතරතුර, අප අපගේ ප්‍රතිදානය පවත්වා ගත යුතුය, ඒ සඳහා ගණන් කිරීමේ අගය 0 ට වඩා අඩු බව අපට පෙනී ගියහොත්, අපි නිෂේධනීය සංඛ්‍යා ගණනය කිරීමේ දර්ශකයේ අගය ප්‍රතිදානයට එකතු කර negative ණ සංඛ්‍යා 1 කින් වැඩි කරන්නෙමු. අපට හමු වූයේ 0 ට වඩා වැඩි හෝ සමාන සංඛ්‍යාවක් පමණි, එබැවින් අපි ධනාත්මක නිම්න දර්ශකයේ අගයන් ප්‍රතිදානයට එකතු කර ධන සංඛ්‍යා ගණනය 1 කින් වැඩි කරන්නෙමු. වැදගත් දෙය නම් මේ දෙකෙහිම එකම අගය සොයා ගන්නා සෑම අවස්ථාවකම හැෂ් අරා වත්මන් දර්ශකය, එයින් අදහස් කරන්නේ අප සඳහා ඊටත් වඩා අමුතු උප-අරාවක් හමු වූ බවයි. අවසානයේදී, අපි ප්‍රතිදානය නැවත ලබා දෙන්නෙමු.

ක්රියාත්මක කිරීම  

එකම ඉරට්ටේ සහ නොගැලපෙන මූලද්‍රව්‍ය සහිත ගණනය කිරීම් සඳහා C ++ වැඩසටහන

#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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

මෙයද බලන්න
කේ මගින් බෙදිය හැකි මුදල සමඟ අරාව යුගල වශයෙන් බෙදීම

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (2n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.