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


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब Facebook गूगल Quora रॉबिन हुड
ऐरे हैश hashing हैश मैप

समस्या का विवरण  

"0 और 1 की समतुल्य संख्या के साथ" सबसे बड़े सबरेरे में, हमने एक दिया है सरणी [[] जिसमें केवल ० और १ है। ० और १ के बराबर संख्या वाला सबसे बड़ा सबर्रे ढूंढें और सबसे बड़े सबरे के स्टार्ट इंडेक्स और एंड इंडेक्स को प्रिंट करेगा।

इनपुट प्रारूप  

पूर्णांक मान वाली पहली पंक्ति N।

दूसरी जगह जिसमें एन स्पेस-अलग-अलग पूर्णांक (0 या 1) हैं।

आउटपुट स्वरूप  

पहली और केवल एक पंक्ति में पूर्णांक मान होता है जो 0 और 1 के XNUMX के बराबर_नंबर के साथ सबसे बड़ी सबरेरी की लंबाई को दर्शाता है।

की कमी  

  • 1 <= एन <= 10 ^ 5
  • 0 <= एक [i] <= 1

उदाहरण  

7
0 1 0 1 1 0 0
6

दृष्टिकोण  

हम चल रहे योग को संग्रहीत करने के लिए एक चर राशि का उपयोग करते हैं जब हम मुठभेड़ करते हैं 1 हम योग में 1 जोड़ते हैं और जब हम 0 का सामना करते हैं तो हम योग में -1 जोड़ते हैं। हम सभी राशि को एक कुंजी-मूल्य जोड़ी के रूप में कुंजी और सूचकांक के रूप में उनकी राशि के साथ एक मानचित्र में संग्रहीत करते हैं। यदि हम उस राशि का सामना करते हैं जो पहले खोजा गया था तो इसका मतलब है कि उस राशि की अंतिम घटना और इस घटना के बीच हमारे पास बराबर संख्या 1 और -1 है। हम सभी का अधिकतम लाभ उठाते हैं।

चलो एक वैरिएबल योग को 0 के बराबर लेते हैं और सरणी के माध्यम से पार करते हैं। हर बार जब हम एक 0 से मिलते हैं, तो हम 1 से घटाते हैं और 1 से बढ़ाते हैं। जब हम मिलते हैं तो 1. यह निष्कर्ष निकालना बहुत आसान है कि हमारे पास एक समान संख्या में 0 और 1 के बराबर संख्या है जब गिनती 0 के बराबर होती है।

चलो एक सरणी अनुक्रम लेते हैं [0, 0, 1, 0, 0, 0, 1, 1]।

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

योग 0 से शुरू होता है और यह -1, -2, -1, -2, -3, -4, -3, -2 होता है

आंकड़े से, हम आसानी से समझ सकते हैं कि समान y- अक्ष मान वाले दो बिंदुओं का संकेत है कि इन दो बिंदुओं के बीच 0 और 1 की समान संख्या है।

0 और 1 के बराबर संख्या के साथ उपश्रेण शुरू हुआ और समाप्त हुआ जब योग -2, -1, और -3 के बराबर हो गया। सबसे लंबा है जब योग -2 के बराबर होता है।

कार्यान्वयन  

0 और 1 के XNUMX के समान संख्या के साथ सबसे बड़ा सबर्रे के लिए C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  map<int,int> m;
    int ans=0,sum=0;
    for(int i=0;i<n;i++){
        int x = a[i];
        sum+=(x==1)?1:-1;
        
        if(sum==0){
        	ans =max(ans,i+1);
        }
        if(m.count(sum)){
            ans = max(ans,i-m[sum]);
        }else{
            m[sum]=i;
        }
    }
    cout<<ans<<endl;
  return 0;
}

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

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_length(arr,n);
        System.out.println(ans);
        
  }
  
  public static int max_length(int[] arr,int n){
    Map<Integer, Integer> m = new HashMap<>();
    	int mx = 0, cnt = 0;
    	for(int i = 0;i < arr.length;i++) {
    		cnt+=(arr[i] == 1)?1:-1;
    		if(cnt == 0)
    			mx = Math.max(mx, i+1);    		
    		if(m.containsKey(cnt)) {
    			mx = Math.max(mx, i - m.get(cnt));
    		} else 
    			m.put(cnt, i);
    	}
    	return mx;
  }
}
9
0 1 1 0 0 1 1 1 0
6

0 और 1 के बराबर संख्या के साथ सबसे बड़ी सबर्रे के लिए जटिलता विश्लेषण  

समय जटिलता

पर) जहां n दिए गए सरणी का आकार है। यहां हम पूरे सरणी को केवल एक बार पार करते हैं और निरंतर समय में प्रत्येक तत्व के लिए ऑपरेशन करते हैं। इसलिए यह हमें रैखिक समय की जटिलता की ओर ले जाता है।

यह भी देखें
खेल कूद

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

पर) जहां n दिए गए सरणी का आकार है। हम स्टोर करने के लिए मैप का उपयोग करते हैं मूल्य के रूप में कुंजी और सूचकांक के रूप में उनकी राशि के साथ सभी योग। और मानचित्र का अधिकतम आकार n है जहां सरणी के सभी मान 0 हैं।