0 आणि 1 च्या समान संख्येसह सर्वात मोठा सबब्रे  


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद फेसबुक Google Quora रॉबिन हूड
अरे हॅश हॅशिंग हॅशमॅप

समस्या विधान  

“0 आणि 1 च्या समान संख्येसह सर्वात मोठा सबब्रे” समस्या मध्ये, आम्ही एक दिले अॅरे अ [] फक्त ० आणि १ असणारा सर्वात मोठा सबराय 0 आणि 1 च्या समान संख्येसह शोधा आणि सर्वात मोठा सबअरेचा प्रारंभ सूचकांक आणि शेवटचा निर्देशांक मुद्रित करेल.

इनपुट स्वरूप  

प्रथम रेखेमध्ये पूर्णांक मूल्य एन.

एन स्पेस-विभक्त पूर्णांक असलेली (० किंवा 0) असलेली दुसरी ओळ.

अंतिम स्वरूप  

प्रथम आणि केवळ एक ओळ ज्यामध्ये 0 आणि 1 च्या समान_ संख्येसह सर्वात मोठ्या सबर्रेची लांबी दर्शवते पूर्णांक मूल्य असते.

मर्यादा  

  • 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, 1, 0, 0, 0, 1, 1].

0 आणि 1 च्या समान संख्येसह सर्वात मोठा सबब्रेपिन

बेरीज 0 पासून सुरू होते आणि या -1, -2, -1, -2, -3, -4, -3, -2 प्रमाणे

आकृतीवरून, आपण सहजपणे समजू शकतो की समान वाय-अक्ष मूल्यासह दोन गुण या दोन बिंदूंमधील अनुक्रम दर्शवितो की समान संख्या 0 आणि 1 आहे.

० आणि १ च्या समान क्रमांकाची सबअरे सुरू झाली आणि संपली जेव्हा बेरीज -२, -१, आणि -0 असते. जेव्हा सर्वात मोठी बेरीज -1 असते.

अंमलबजावणी  

0 आणि 1 च्या समान संख्येसह सर्वात मोठ्या सबबर्रेसाठी सी ++ प्रोग्राम

#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 च्या समान संख्येसह सबब्रेसाठी जटिलता विश्लेषण  

वेळ कॉम्प्लेक्सिटी

O (n) जेथे n दिलेल्या अ‍ॅरेचा आकार आहे. येथे आम्ही संपूर्ण अ‍ॅरे केवळ एक वेळ पार करतो आणि प्रत्येक घटकासाठी सतत वेळेत ऑपरेशन करतो. म्हणूनच हे आपल्याला वेळेची जटिलता आणते.

हे सुद्धा पहा
जंप गेम

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे n दिलेल्या अ‍ॅरेचा आकार आहे. आम्ही संग्रहित करण्यासाठी नकाशा वापरतो त्यांची बेरीज आणि मूल्य म्हणून निर्देशांक म्हणून सर्व बेरीज. आणि अ‍ॅरेची सर्व मूल्ये 0 आहेत जेथे नकाशाचा अधिकतम आकार n आहे.