0 और 1 एस के बराबर संख्या के साथ सबसे बड़ा सबर्रे


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना Coursera ग्रेओरेन्ज MakeMyTrip मॉर्गन स्टेनली Paytm Synopsys टाइम्स इंटरनेट
ऐरे हैश

आपको एक पूर्णांक दिया गया है। पूर्णांक इनपुट सरणी में केवल 0 और 1 हैं। समस्या कथन सबसे बड़े उप-सरणी का पता लगाने के लिए कहता है जिसमें 0 और 1s की समान संख्या हो सकती है।

उदाहरण

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

व्याख्या

सरणी स्थिति 0 से 5 तक 0 और 1s के बराबर नहीं थी

0 की गिनती 3

1 की गिनती ⇒ 3

और यह सबसे बड़ा उप-सरणी है जो 0 और 1s के बराबर है।

एल्गोरिदम सबसे बड़ी संख्या में 0 और 1 एस के साथ सबसे बड़ा सबर्रे को खोजने के लिए

  1. डिक्लेयर ए हैश मैप.
  2. सेट योग, अधिकतम लंबाई, शुरुआत 0 और EndIndex -1 को।
  3. सरणी को ट्रैव करें और सरणी के प्रत्येक तत्व को -1 के रूप में अपडेट करें यदि यह 0 के बराबर है।
  4. 0 से n-1 (एन सरणी की लंबाई है) से लूप शुरू करें।
    1. गिरफ्तारी के प्रत्येक मूल्य को [i] जोड़ दें।
    2. जाँच करें कि क्या योग 0 के बराबर है, यदि सही है,
      1. फिर अपडेट करें अधिकतम लंबाई i + 1 के रूप में, और EndIndex मैं के रूप में
    3. जाँच करें कि क्या मानचित्र में इसका योग + n है,
      1. फिर मान के रूप में अधिकतम लंबाई की लंबाई को अपडेट करें - मानचित्र से नक्शा (राशि + एन) और अंत में मैं के रूप में।
    4. Else ने उस राशि + n को मानचित्र में रखा।
  5. प्रिंट एंडइंडेक्स - अधिकतम गति 1 और एंड आईंडेक्स।

व्याख्या

एक सरणी को देखते हुए और हमें 0 और 1s के बराबर संख्या के साथ सबसे बड़े उप-सरणी का पता लगाने के लिए कहा जाता है। उप-सरणी की सीमा ज्ञात करें ताकि यह सभी उप-सरणियों की सभी लंबाई के बीच सबसे बड़ा हो जो 0 और 1 के बराबर संख्या रखता है। हम इसका उपयोग करेंगे हैश मैप भंडारण के लिए पूर्णांक इसमें मूल्य हैं। hashing एक कुशल दृष्टिकोण और बेहतर समय जटिलता प्रदान करता है। मान लो योग, अधिकतम लंबाई जैसे 0 तब हम इसे कोड में एक साथ अपडेट करने जा रहे हैं। हमारे पास एक वैरिएबल होगा, जिसे एंडइंडेक्स कहा जाता है, यह उस रेंज के अंतिम बिंदु का मान रखेगा, जहां सब-ऐरन एंड्स की रेंज की अधिकतम लंबाई होनी चाहिए।

सरणी को पीछे छोड़ें, यह जानने के लिए कि क्या सरणी का कोई मान 0 के बराबर है, तो हम इसे -1 के रूप में चिह्नित करेंगे, और सरणी मान को छोड़ देंगे जो इसमें 1 है। क्योंकि यहां हम वास्तविक सीमा का पता लगाने वाले नहीं हैं। तर्क शून्य की संख्या को गिनना है और जिनका अर्थ लंबाई सीमा भी है। इसलिए हम 0 को -1 के रूप में चिह्नित करेंगे, और जब हम ऐरे के भीतर मान जोड़ेंगे। यदि हम योग को 0 के रूप में पाते हैं, तो इसका मतलब है कि हमें एक जोड़ी समान और शून्य मिली है, क्योंकि प्रत्येक -1 और 1 0 बनाते हैं, क्योंकि हम प्रत्येक 0 को -1 के रूप में चिह्नित करते हैं, इसलिए हम इसे गिन सकते हैं।

हम किसी सरणी में प्रत्येक मान को योग करने जा रहे हैं, और पाते हैं कि क्या यह 0 के बराबर है, यदि समान है तो सरणी के अधिकतम लंबाई और समाप्ति बिंदु को अपडेट करें। हम मानचित्र में राशि + n डालने जा रहे हैं यदि यह पहले से मौजूद नहीं है, और यदि यह मौजूद है तो कुछ शर्तों की जांच करें और फिर अधिकतम गति और समाप्ति बिंदु के मान को अपडेट करें। प्रिंट एंडइंडेक्स - अधिकतम गति 1 और रेंज के शुरुआती बिंदु के रूप में एंडिंगडेक्स रेंज के अंतिम बिंदु के रूप में।

0 और 1 एस के बराबर संख्या के साथ सबसे बड़ा सबर्रे

कोड

C ++ कोड 0 और 1s के बराबर संख्या के साथ सबसे बड़ा सबर्रे खोजने के लिए

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

जावा में कार्यान्वयन 0 और 1 एस की समान संख्या के साथ सबसे बड़ा सबरेरा खोजने के लिए

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। यहाँ हम इस समस्या को O (n) में हल कर सकते हैं क्योंकि हमने HashMap का उपयोग किया है। क्योंकि HashMap O (1) समय जटिलता में तत्वों को सम्मिलित, हटा या संशोधित कर सकता है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। चूंकि हैशमैप में सबसे खराब स्थिति में डाले जाने वाले तत्वों की संख्या सबसे अधिक n होगी। यह रैखिक अंतरिक्ष जटिलता हासिल की है।