పరస్పర శ్రేణి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ MakeMyTrip మోర్గాన్ స్టాన్లీ Paytm
హ్యాషింగ్ స్లైడింగ్ విండో

ఒక ఇవ్వబడింది అమరిక సంఖ్య 0 మరియు 1 లను మాత్రమే కలిగి ఉంటుంది. O మరియు 1 లతో సమానంగా ఉండే పొడవైన వరుస ఉప-శ్రేణి యొక్క పొడవును మనం కనుగొనాలి.

ఉదాహరణ

ఇన్పుట్

arr = [0,1,0,1,0,0,1]

అవుట్పుట్

6

వివరణ

అతి పొడవైన పరస్పర ఉప-శ్రేణి ఎరుపు రంగులో గుర్తించబడింది [0,1,0,1,0,0,1] మరియు దాని పొడవు 6.

అల్గారిథం

  1. మాక్స్లెన్ విలువను 0 కి సెట్ చేయండి.
  2. రెండు లూప్‌లను ఉపయోగించండి, మొదటి లూప్‌లో zer_count 0 కు, ఒక_కౌంట్ 0 కు సెట్ చేయండి.
  3. విలువ ఉంటే నిర్దిష్ట సూచిక వద్ద శ్రేణి 0 అని తేలితే సున్నా_కౌంట్‌ను 1 పెంచండి.
  4. లేకపోతే అప్‌డేట్ చేయండి మరియు వన్_కౌంట్‌ను 1 పెంచండి.
  5. ప్రతి పునరావృత తనిఖీలో సున్నా_కౌంట్ వన్_కౌంట్కు సమానంగా ఉందా, సమానంగా ఉంటే, మధ్య పెద్ద సంఖ్యను కనుగొనండి (మాక్స్లెన్ మరియు జె-ఐ + 1)
  6. గరిష్టంగా తిరిగి

వివరణ

మా ప్రధాన ఆలోచన సున్నా మరియు ఒకదానిని మాత్రమే కలిగి ఉన్న పొడవైన వరుస సబారే యొక్క పొడవును కనుగొనడం, కాబట్టి మా ప్రధాన దృష్టి ఆ పొడవును కనుగొనడం.

అందువల్ల, మేము లూప్ కోసం సమూహాన్ని ఉపయోగించబోతున్నాము. బాహ్య లూప్‌లో, మేము సున్నా_కౌంట్ మరియు వన్_కౌంట్ యొక్క విలువను 0 కి ప్రారంభిస్తాము, ఎందుకంటే ప్రతి పునరావృతం తర్వాత లోపలి లూప్ నుండి బయటకు వచ్చినప్పుడు మనకు సున్నా_కౌంట్ యొక్క తాజా విలువలు మరియు దానిపై మళ్లీ తనిఖీ చేయడానికి వన్_కౌంట్ అవసరం. శ్రేణి యొక్క పొడవు వచ్చే వరకు మేము లూప్ మీద మళ్ళించబోతున్నాము.

ఇప్పుడు అది శ్రేణి యొక్క ప్రతి విలువను తనిఖీ చేయబోతోంది, అర్ర్ [ఇండెక్స్] విలువ 0 లేదా 1 కలిగి ఉంటే అది 0 కి సమానమైన విలువను కలిగి ఉంటే, అప్పుడు అప్‌డేట్ చేయండి మరియు జీరో_కౌంట్ విలువను 1 పెంచండి లేదా అర్ [ఇండెక్స్] విలువ ఉంటే 1 గా కనుగొనబడింది, అప్పుడు అది నవీకరించబడుతుంది మరియు వన్_కౌంట్ విలువను 1 పెంచుతుంది.

ఇప్పుడు, సున్నా_కౌంట్ వన్_కౌంట్కు సమానంగా ఉందో లేదో తనిఖీ చేయబోతున్నట్లయితే, సమానమైతే, మాక్స్లెన్ మరియు జె-ఐ + 1 మధ్య పెద్ద సంఖ్యను కనుగొని, పెద్ద సంఖ్యను మాక్స్లెన్లో నిల్వ చేస్తుంది.

ఉదాహరణ

ఇచ్చిన శ్రేణి అనుకుందాం: arr [] = 1,0,0,1,0,1,0 XNUMX}

సున్నా_కౌంట్ = 0, వన్_కౌంట్ = 0, మాక్స్లెన్ = 0

i = 0, => j = i వద్ద

j = 0

arr [j] వద్ద 0 కి సమానం కాదు, అప్పుడు one_count ++, అంటే one_count = 1

j = 1

Ar [j] వద్ద 0 కి సమానం, అప్పుడు సున్నా_కౌంట్ ++, అంటే సున్నా_కౌంట్ = 1

బ్లాక్ అమలు చేయబడితే ఈ స్థలంలో, ఇది మాక్స్లెన్ మరియు j-i + 1 మధ్య పెద్ద సంఖ్యను ఇవ్వదు మరియు మాక్స్లెన్లో 2 ని తిరిగి ఇస్తుంది

j = 2

Ar [j] వద్ద 0 కి సమానం, అప్పుడు సున్నా_కౌంట్ ++, అంటే సున్నా_కౌంట్ = 2

j = 3

అర్ [j] వద్ద 0 కి సమానం కాదు, అప్పుడు వన్_కౌంట్ ++, అంటే వన్_కౌంట్ = 2

బ్లాక్ అమలు చేయబడితే ఈ స్థలంలో, ఇది మాక్స్లెన్ మరియు j-i + 1 ల మధ్య పెద్ద సంఖ్యను ఇవ్వదు మరియు మాక్స్లెన్లో 4 ని తిరిగి ఇస్తుంది.

j = 4

Ar [j] వద్ద 0 కి సమానం, అప్పుడు సున్నా_కౌంట్ ++, అంటే సున్నా_కౌంట్ = 3

j = 5

అర్ [j] వద్ద 0 కి సమానం కాదు, అప్పుడు వన్_కౌంట్ ++, అంటే వన్_కౌంట్ = 3

బ్లాక్ అమలు చేయబడితే ఈ స్థలంలో, ఇది మాక్స్లెన్ మరియు j-i + 1 ల మధ్య పెద్ద సంఖ్యను ఇవ్వదు మరియు మాక్స్లెన్లో 6 ని తిరిగి ఇస్తుంది.

j = 6

Ar [j] వద్ద 0 కి సమానం, అప్పుడు సున్నా_కౌంట్ ++, అంటే సున్నా_కౌంట్ = 4

మరియు అన్ని పరిస్థితులు విఫలమయ్యే వరకు ఇది లూప్‌ను మళ్ళిస్తుంది.

మరియు మాక్స్లెన్‌ను 6 గా తిరిగి ఇవ్వండి.

అమలు

పరస్పర శ్రేణి కోసం C ++ ప్రోగ్రామ్

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

పరస్పర శ్రేణి కోసం జావా ప్రోగ్రామ్

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

పరస్పర శ్రేణి కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N * N) (ఇక్కడ N ఇచ్చిన శ్రేణి యొక్క పరిమాణం.

అంతరిక్ష సంక్లిష్టత

O (1) ఎందుకంటే మేము ఇక్కడ అదనపు స్థలాన్ని ఉపయోగించము.

సూచన