Броји подниз са једнаким бројем 1 и 0


Ниво тешкоће Лако
Често питани у Цисцо ЦоупонДуниа Цоурсера Датабрицкс карат САП Лабс Тесла
Ред Хасх

Изјава о проблему

Проблем „Броји поднизове са једнаким бројем 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).

Алгоритам

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. Користићемо Хасхинг. Прогласићемо а Мапа. На мапи ћемо збројити зброј и његову учесталост као 1. Ако је нов на мапи, додајте је на мапу, у супротном повећајте учесталост вредности претходног збира која је присутна на мапи.

Али пре тога, претворићемо све 0 у -1, док ћемо обилазити петљу. Ако смо пронашли елемент низа као 0, претворићемо га у -1. Збрајање вредности тренутног елемента низа у збир. Проверићемо збир, ако је збир једнак 0, повећаћемо вредност резултата. То је зато што претварамо све 0 у -1 и имамо само 1 и 0. Дакле, када претворимо 0 у -1 и додамо ту вредност са 1с. Кад год је збир 0, то је могуће само када имамо једнаке 0 и 1.

Претпоставимо да имамо три јединице и три јединице 1, и претварајући сваку 0 у -0 и сабирајући три 1 и три -1, добићемо 1 као збир. То такође подразумева да би након конверзије 0 у -0, да бисмо имали 1 као збир, требало да имамо једнаке 0 и 0. Дакле, кад год нађемо вредност збира као 1, повећаћемо излазну вредност. Узимајући у обзир улазни низ, ажурираћемо вредност излаза кад год добијемо суму као 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

Анализа сложености

Време Ц0мплекити

Он) где „Н“ је број елемената у низу. Будући да смо користили ХасхМап, можемо постићи линеарну временску сложеност.

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

Он) где „Н“ је број елемената у низу. Овде смо у ХасхМап-у сачували збир као кључ, чиме се постиже линеарна сложеност простора.