په دوه بائنري تیرونو کې د ورته Sum سره اوږده موده


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي Accenture سیسکو په حقیقت کی کولیزا د SAP لابراتوارونه Yandex
پیشه هاش ځورول

ستونزه بیان

تاسو ته دوه تیرونه درکول کیږي چې له دې جملې څخه هر یو د بائنری نمبر لري. د ستونزې بیان غوښتنه کوي چې د دوه بائنري اریونو کې ورته جمع سره د اوږدې مودې موندلو لپاره ، دا دا چې د (i ، j) څخه د اعظمي اوږدوالي عمومي فرعي سرې په دې ډول ومومئ چې j له i او arr1 سره لوی وي یا مساوي وي [ i] + ارار 1 [i + 1] + ارار 1 [i + 2] +…. + arr1 [j] = arr2 [i] + arr2 [i + 1] + arr2 [i + 2] +…. + arr2 [j].

بېلګه

arr1[] = {1,0,1,0,0,0,1,1}

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

توضیحي: د ترټولو عام دورې اوږدوالی 4 دی ځکه چې د 0 څخه تر 3 پورې شاخص کې د دواړه فرعي سرېونو مجموعه مساوي ده.

په دوه بائنري تیرونو کې د ورته Sum سره اوږده موده

arr1[] = {1, 0, 1, 0, 1, 0}

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

توضیحي: د ترټولو عام دورې اوږدوالی 4 دی ځکه چې د 0 څخه تر 3 پورې شاخص کې د دواړه فرعي سرنو مجموعه ده.

 

الګوریتم

1. Declare an array of size n.
2. Find the difference of each element’s index of both of the arrays such that arr[i]=arr1[i]-arr2[i].
3. Declare the HashMap.
4. Set sum to 0 and maxLength to 0.
5. From i=0 to i<n.
    1. Add up the value of arr[i] and sum into the sum.
    2. Check if sum ==0, then update the maxLength=i+1.
    3. Check if the map contains the sum, then update the maxLength to the maximum between maxLength and i-key’s value.
    4. Else put the sum and its index into the map.
6. Return maxLength.

تشریح

موږ دوه دوه بائنري تیرونه ورکړي ، چې هر یو یې د بائنری شمیره د 0 او 1 په ب containsه کې لري. موږ باید د [i ، j] تر ټولو اوږد مشترک دوره ومومو چې په هغه ځانګړي موده کې د دواړو لارو ارزوګانې. ، مساوي دي او د دې اوږدوالي اوږدوالی یې اوږد دی. د دې لپاره ، موږ موږ ته هاشینګ او یو اضافي سرنی ته ځو په کوم کې چې موږ د هر لیست شوي عنصر توپیر توپیر ذخیره کوو د رامینځته شوي ځای په ځای کې.

موږ یوه نقشه رامینځته کوو ، پدې کې موږ د نوي رامینځته شوي ارزښت ارزښت په نقشه کې د کیلي په توګه او د ارزښت په توګه د دې شاخص ساتو. موږ د دې شاخص اعظمي حد موندلو او د میکس لینت سره پرتله کولو ته لاړو چې موږ رامینځته کړی ترڅو ترټولو اوږد اوږدوالي په توګه اعظمي ارزښت ومومئ. مګر د هغې دمخه ، موږ آرر غوره کوو [i] او دا د آرر [i] سره اضافه کوو او مجموعه او په لنډیز کې یې ذخیره کوو. موږ به وګورو چې دا رقم 0 سره مساوي دی ، میک لاینتیت i + 1 ته تازه کړئ. دا په وروستي شاخص عنصر کې د ارزښتونو اداره کول دي.

وګورئ چې که نقشه کې مجموعه شتون لري ، نو بیا د اعظمي حد او د اعظمي درجې او شاخص تر مینځ د موندلو له لارې اعظمي اوږدوالی تازه کړئ - نقشه[جمع]. او یا هم نقشه کې برخه او شاخص دننه کړئ. هغه سري چې موږ یې جوړه کړې او پیل یې کړی د دواړو تیرونو ترمنځ توپیر کلیدي رول لوبوي. له دې وروسته ، موږ په مکس لینت کې ارزښت لرو او مایک لینت ته راستنیدو.

 

د دوه بائنري تیرونو کې ورته ورته سره د اوږدې مودې سپین موندلو لپاره کوډ

C ++ کوډ

#include<iostream>
#include<unordered_map>

using namespace std;

int longestCommonSum(int arr1[], int arr2[], int n)
{
    int arr[n];
    for (int i=0; i<n; i++)
        arr[i] = arr1[i] - arr2[i];

    unordered_map<int, int> hM;

    int sum = 0;

    int max_len = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];

        if (sum == 0)
            max_len = i + 1;

        if (hM.find(sum) != hM.end())
            max_len = max(max_len, i - hM[sum]);

        else
            hM[sum] = i;
    }
    return max_len;
}

int main()
{
    int arr1[] = {0, 1, 0, 1, 1, 1, 1};
    int arr2[] = {1, 1, 1, 1, 1, 0, 1};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout << longestCommonSum(arr1, arr2, n);
    return 0;
}
6

 

جاوا کوډ

import java.util.HashMap;

class LargestSubArr01
{
    public static int longestCommonSum(int[] arr1, int[] arr2, int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = arr1[i] - arr2[i];

        HashMap<Integer, Integer> hM = new HashMap<>();

        int sum = 0;
        int max_len = 0;

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];

            if (sum == 0)
                max_len = i + 1;

            if (hM.containsKey(sum))
                max_len = Math.max(max_len, i - hM.get(sum));

            else
                hM.put(sum, i);
        }
        return max_len;
    }
    public static void main(String args[])
    {
        int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
        int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
        int n = arr1.length;
        System.out.println(longestCommonSum(arr1, arr2, n));
    }
}
6

 

د پیچلتیا تحلیل

د وخت پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. دلته ، موږ یوځل صف تیر کړی ، او دا چې موږ غیر منظمه نقشه کارولې ده. اضافه کول ، حذف کول ، او د لټون عملیات د O (1) وخت پیچلتیا لري. پدې توګه ، په دوه بائنري لارو کې د ورته مقدار سره د اوږدې مودې لپاره بشپړ الګوریتم د وخت وخت پیچلتیا لري.

د ځای پیچلتیا

له هغه ځایه چې موږ غیر منظم_ نقشه یا د هیش نقشه کارولې ، نو موږ هم د خط خطي پیچلتیا لرو. اې (N) هلته "n" په صف کې د عناصرو شمیر دی.