തുടർച്ചയായ അറേ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ 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 എന്നും ഒരു_ക ount ണ്ട് 0 എന്നും സജ്ജമാക്കുക.
  3. ന്റെ മൂല്യം എങ്കിൽ ഒരു പ്രത്യേക സൂചികയിലെ ശ്രേണി 0 ആണെന്ന് കണ്ടെത്തി തുടർന്ന് പൂജ്യം_കൗണ്ട് 1 വർദ്ധിപ്പിക്കുക.
  4. അല്ലെങ്കിൽ അപ്‌ഡേറ്റ് ചെയ്‌ത് ഒരു_ക ount ണ്ട് 1 വർദ്ധിപ്പിക്കുക.
  5. ഓരോ ആവർത്തന പരിശോധനയിലും പൂജ്യം_ക ount ണ്ട് ഒരു_ക ount ണ്ടിന് തുല്യമാണോ, തുല്യമാണെങ്കിൽ, അതിനിടയിലുള്ള വലിയ എണ്ണം കണ്ടെത്തുക (മാക്സ്ലെൻ, ജെ-ഐ + 1)
  6. മാക്‌സ്‌ലെൻ മടങ്ങുക

വിശദീകരണം

ഞങ്ങളുടെ പ്രധാന ആശയം പൂജ്യവും ഒരാളുടെ മാത്രം ദൈർഘ്യവുമുള്ള ഏറ്റവും ദൈർഘ്യമേറിയ തുടർച്ചയായ സബ്‌റേയുടെ നീളം കണ്ടെത്തുക എന്നതാണ്, അതിനാൽ ഞങ്ങളുടെ പ്രധാന ശ്രദ്ധ ആ നീളം കണ്ടെത്തുക എന്നതാണ്.

അതിനാൽ, ഞങ്ങൾ ലൂപ്പിനായി നെസ്റ്റഡ് ഉപയോഗിക്കാൻ പോകുന്നു. ബാഹ്യ ലൂപ്പിൽ, ഞങ്ങൾ പൂജ്യം_ക ount ണ്ടിന്റെയും ഒരു_ക ount ണ്ടിന്റെയും മൂല്യം 0 ആയി സമാരംഭിക്കുന്നു, കാരണം ഓരോ ആവർത്തനത്തിനും ശേഷം ആന്തരിക ലൂപ്പിൽ നിന്ന് പുറത്തുവരുമ്പോൾ നമുക്ക് പൂജ്യം_ക ount ണ്ടിന്റെ പുതിയ മൂല്യങ്ങളും വീണ്ടും പരിശോധിക്കുന്നതിന് ഒരു_ക ount ണ്ടും ആവശ്യമാണ്. അറേയുടെ ദൈർഘ്യം എത്തുന്നതുവരെ ഞങ്ങൾ ലൂപ്പിന് മുകളിലൂടെ ആവർത്തിക്കാൻ പോകുന്നു.

ഇപ്പോൾ അത് അറേയുടെ ഓരോ മൂല്യവും പരിശോധിക്കാൻ പോകുന്നു, arr [index] ന് 0 അല്ലെങ്കിൽ 1 എന്ന മൂല്യമുണ്ടെങ്കിൽ അതിന് 0 ന് തുല്യമായ ഒരു മൂല്യമുണ്ടെങ്കിൽ, അപ്ഡേറ്റ് ചെയ്ത് പൂജ്യം_ക ount ണ്ടിന്റെ മൂല്യം 1 വർദ്ധിപ്പിക്കുക അല്ലെങ്കിൽ arr [index] ന്റെ മൂല്യം ആണെങ്കിൽ. 1 ആണെന്ന് കണ്ടെത്തി, അത് അപ്‌ഡേറ്റ് ചെയ്യുകയും ഒരു_ക ount ണ്ടിന്റെ മൂല്യം 1 വർദ്ധിപ്പിക്കുകയും ചെയ്യുന്നു.

ഇപ്പോൾ, അടുത്തത് ബ്ലോക്ക് സീറോ_ക ount ണ്ട് ഒരു_ക ount ണ്ടിന് തുല്യമാണോയെന്ന് പരിശോധിക്കാൻ പോകുന്നു, തുല്യമാണെങ്കിൽ, മാക്സ്ലെനും ജെ-ഐ + 1 ഉം തമ്മിലുള്ള വലിയ സംഖ്യ കണ്ടെത്തി മാക്സ്ലെനിൽ വലിയ സംഖ്യ സംഭരിക്കുന്നു.

ഉദാഹരണം

നൽകിയ ശ്രേണി കരുതുക: arr [] = 1,0,0,1,0,1,0 XNUMX}

പൂജ്യം_ക = ണ്ട് = 0, ഒരു_ക = ണ്ട് = 0, പരമാവധി = 0

i = 0, => j = i

j = 0

arr [j] 0 ന് തുല്യമല്ല, തുടർന്ന് ഒരു_ക ++ ണ്ട്, അതായത് ഒരു_ക = ണ്ട് = 1 എന്നാണ്

j = 1

Ar [j] 0 ന് തുല്യമാണ്, തുടർന്ന് പൂജ്യം_ക ++ ണ്ട്, അതായത് പൂജ്യം_ക = ണ്ട് = 1

അടുത്ത സ്ഥലത്ത് ഈ സ്ഥലത്ത് ബ്ലോക്ക് എക്സിക്യൂട്ട് ചെയ്താൽ, അത് മാക്സ്ലെൻ, j-i + 1 എന്നിവയ്ക്കിടയിൽ വലിയ എണ്ണം നൽകുന്നില്ല, കൂടാതെ മാക്സ്ലെനിൽ 2 നൽകുന്നു

j = 2

Ar [j] 0 ന് തുല്യമാണ്, തുടർന്ന് പൂജ്യം_ക ++ ണ്ട്, അതായത് പൂജ്യം_ക = ണ്ട് = 2

j = 3

Ar [j] 0 ന് തുല്യമല്ല, പിന്നെ one_count ++, അതായത് one_count = 2

അടുത്ത സ്ഥലത്ത് ഈ സ്ഥലത്ത് ബ്ലോക്ക് എക്സിക്യൂട്ട് ചെയ്താൽ, അത് മാക്സ്ലെൻ, j-i + 1 എന്നിവയ്ക്കിടയിൽ വലിയ എണ്ണം നൽകുന്നില്ല, കൂടാതെ മാക്സ്ലെനിൽ 4 നൽകുന്നു.

j = 4

Ar [j] 0 ന് തുല്യമാണ്, തുടർന്ന് പൂജ്യം_ക ++ ണ്ട്, അതായത് പൂജ്യം_ക = ണ്ട് = 3

j = 5

Ar [j] 0 ന് തുല്യമല്ല, പിന്നെ one_count ++, അതായത് one_count = 3

അടുത്ത സ്ഥലത്ത് ഈ സ്ഥലത്ത് ബ്ലോക്ക് എക്സിക്യൂട്ട് ചെയ്താൽ, അത് മാക്സ്ലെൻ, j-i + 1 എന്നിവയ്ക്കിടയിൽ വലിയ എണ്ണം നൽകുന്നില്ല, കൂടാതെ മാക്സ്ലെനിൽ 6 നൽകുന്നു.

j = 6

Ar [j] 0 ന് തുല്യമാണ്, തുടർന്ന് പൂജ്യം_ക ++ ണ്ട്, അതായത് പൂജ്യം_ക = ണ്ട് = 4

എല്ലാ നിബന്ധനകളും പരാജയപ്പെടുന്നതുവരെ ഇത് ലൂപ്പ് ആവർത്തിക്കുന്നു.

മാക്‌സ്‌ലെൻ 6 ആയി മടങ്ങുക.

നടപ്പിലാക്കൽ

തുടർച്ചയായ അറേയ്ക്കുള്ള സി ++ പ്രോഗ്രാം

#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) കാരണം ഞങ്ങൾ ഇവിടെ അധിക സ്ഥലമൊന്നും ഉപയോഗിക്കുന്നില്ല.

അവലംബം