1 اور 0 کے مساوی نمبر والے سبریوں کی گنتی کریں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے سسکو کوپنڈونیا Coursera ڈیٹا بکس کرات SAP لیبز Tesla
لڑی ہیش

مسئلہ یہ بیان

مساوی "سبریوں کو 1 اور 0's کی مساوی تعداد کے ساتھ" شمار کرتا ہے کہ آپ کو صرف 0 اور 1 کی ایک صف ملتی ہے۔ مسئلہ بیان میں ذیلی ارای کی گنتی کا پتہ لگانے کے لئے کہا جاتا ہے جس میں 0 کے اشتہار 1 کے برابر نمبر ہوتے ہیں۔

مثال کے طور پر

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

وضاحت: تمام ذیلی ارای (1,2،3,4)، (0,3،1,4)، (XNUMX،XNUMX)، (XNUMX،XNUMX) ہیں

1 اور 0 کے مساوی نمبر والے سبریوں کی گنتی کریں

 

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

وضاحت: تمام ذیلی ارای (0 ، 1) ، (2,3،0,3) ، (1,4،0,5) ، (4,5،2,5) ، (XNUMX،XNUMX) ، (XNUMX،XNUMX) ، (XNUMX،XNUMX) ہیں۔

الگورتھم

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 کو -1 میں تبدیل کردیں گے ، جبکہ لوپ کو عبور کرتے ہوئے ، اگر ہمیں کوئی صف عنصر 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 کے مساوی نمبر والے سبریوں کو گننے کے لئے C ++ کوڈ

#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

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم نے ہش میپ کا استعمال کیا ہے لہذا ہم لین ٹائم پیچیدگی حاصل کرنے کے اہل ہیں۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ یہاں ہاشمیپ میں ہم نے کلیدی حیثیت سے رقم کی بچت کی ہے ، اس طرح خلا کی پیچیدگی پیدا ہوجاتی ہے۔