1 અને 0 ની સમાન સંખ્યાવાળા સબઅર્રેઝની ગણતરી કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે સિસ્કો કુપનદુનિયા Coursera ડેટાબેક્સ કરાત એસએપી લેબ્સ ટેસ્લા
અરે હેશ

સમસ્યા નિવેદન

સમસ્યા "1 અને 0 ની સમાન સંખ્યાવાળી સબએરાઇઝ ગણતરી કરો" જણાવે છે કે તમને ફક્ત 0 અને 1 નો સમાવેશ થાય છે. સમસ્યા નિવેદનમાં 0 ની જાહેરાત 1 ની સમાન નંબરની પેટા એરેની ગણતરી શોધવા માટે પૂછવામાં આવે છે.

ઉદાહરણ

arr[] = {0, 0, 1, 1, 0}
4

સમજૂતી: બધી પેટા એરે (1,2), (3,4), (0,3), (1,4) છે

1 અને 0 ની સમાન સંખ્યાવાળા સબઅર્રેઝની ગણતરી કરો

 

arr[] = {1,0,0,1,1,0}
7

સમજૂતી: તમામ પેટા એરે (0, 1), (2,3), (0,3), (1,4), (0,5), (4,5), (2,5) છે.

અલ્ગોરિધમ

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

સમજૂતી

અમે ફક્ત 0 અને 1 નો સમાવેશ કરેલો એરે આપ્યો છે. તેથી, આપણે પેટા-એરેની ગણતરી શોધવાની જરૂર છે જેમાં ફક્ત 0 અને 1 જ છે. અમે ઉપયોગ કરવા જઇ રહ્યા છીએ હેશિંગ. અમે જાહેર કરીશું a નકશો. નકશામાં, આપણે સરવાળો અને તેની આવર્તન 1 તરીકે સંગ્રહવા જઈ રહ્યા છીએ. જો તે નકશામાં નવો છે તો તેને નકશામાં ઉમેરો, નહીં તો નકશામાં અગાઉના સરવાળોના મૂલ્યની આવર્તન વધારવી.

પરંતુ તે પહેલાં, આપણે બધા 0's ને -1 માં રૂપાંતરિત કરીશું, જ્યારે લૂપને ટ્રversવર્સ કરી રહ્યા છીએ, જો આપણને એરે એલિમેન્ટ 0 તરીકે મળ્યું છે, તો આપણે તેને -1 માં કન્વર્ટ કરીશું. સરવાળોમાં વર્તમાન એરે તત્વનું મૂલ્ય ઉમેરવું. આપણે સરવાળાની તપાસ કરીશું, જો સરવાળો 0 ની બરાબર છે, તો આપણે આઉટપુટનું મૂલ્ય વધારીશું. આ એટલા માટે છે કે આપણે બધા 0 ને -1 માં રૂપાંતરિત કરી રહ્યા છીએ અને આપણી પાસે ફક્ત 1 અને 0 છે. તેથી જ્યારે આપણે 0 માં -1 માં રૂપાંતરિત કરીએ અને તે મૂલ્ય 1s સાથે ઉમેરીએ. જ્યારે પણ સરવાળો 0 હોય, ત્યારે તે ત્યારે જ શક્ય બને જ્યારે આપણી પાસે 0 અને 1 હોય.

માની લો કે આપણી પાસે ત્રણ 1 અને ત્રણ 0 છે, અને દરેક 0 ને -1 માં રૂપાંતરિત કરીશું અને ત્રણ 1 અને ત્રણ -1 ઉમેરીશું, તો આપણી પાસે 0 ની રકમ હશે. આનો અર્થ પણ સૂચવે છે કે 0 ને -1 માં રૂપાંતરિત કર્યા પછી, 0 તરીકે સરવાળો કરવા માટે, આપણી પાસે 0 અને 1 બરાબર હોવું જોઈએ. તેથી, જ્યારે પણ તમે સરવાળોનું મૂલ્ય 0 તરીકે મેળવશો, અમે આઉટપુટ મૂલ્યમાં વધારો કરીશું. ઇનપુટ એરેને ધ્યાનમાં રાખીને, જ્યારે પણ આપણને સરવાળો 0 મળે ત્યારે આપણે આઉટપુટનું મૂલ્ય અપડેટ કરીશું.

કોડ

1 અને 0 ની સમાન સંખ્યાવાળા સબએરાઇઝને ગણતરી માટે સી ++ કોડ

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}
Sub-Arrays with equal 0's and 1's count is: 4

1 અને 0 ની સમાન સંખ્યાવાળા સબએરેય્સને ગણતરી માટે જાવા કોડ

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}
Sub-Arrays with equal 0's and 1's count is:4

જટિલતા વિશ્લેષણ

સમય C0mplexity

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે અમે હેશમેપનો ઉપયોગ કર્યો છે અમે રેખીય સમય જટિલતા પ્રાપ્ત કરવામાં સક્ષમ છીએ.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. અહીં હેશમેપમાં આપણે સરવાળો કી તરીકે સાચવ્યો છે, આમ રેખીય અવકાશ જટિલતા પ્રાપ્ત થાય છે.