1 സെ എണ്ണമുള്ള ഏറ്റവും ദൈർഘ്യമേറിയ സബ്‌റേ 0 സെ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് ആമസോൺ ഡി.ഇ.ഷാ സാംസങ്
അറേ ഹാഷ്

ഞങ്ങൾ ഒരു നൽകി ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ. ഒരു അറേയിൽ 1 ഉം 0 ഉം മാത്രം അടങ്ങിയിരിക്കുന്നു. 1 ന്റെ അക്കത്തിന്റെ അളവ് ഒരു ഉപ-അറേയിലെ 0 ന്റെ എണ്ണത്തേക്കാൾ ഒന്ന് മാത്രമുള്ള ദൈർഘ്യമേറിയ ഉപ-അറേയുടെ ദൈർഘ്യം കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

ഇൻപുട്ട്:

arr [] = {1,0,1,1,0,0,0}

ഔട്ട്പുട്ട്:

5

വിശദീകരണം:

0 മുതൽ 4 വരെ സൂചിക, {1, 0, 1, 1, 0}, മൂന്ന് ഉണ്ട് 1 ഉം രണ്ട് 0 ഉം. 1-നേക്കാൾ 0 ന്റെ ഒരു എണ്ണം കൂടി.

ഇൻപുട്ട്:

arr [] = {1,0,1,0,0}

ഔട്ട്പുട്ട്:

3

വിശദീകരണം:

0 മുതൽ 2 വരെ സൂചിക, {1, 0, 1}, രണ്ട് 1 ഉം ഒരു 0 ഉം ഉണ്ട്. 1-നേക്കാൾ 0 ന്റെ ഒരു എണ്ണം കൂടി.

അൽഗോരിതം

  1. ഒരു മാപ്പ് പ്രഖ്യാപിക്കുക.
  2. സംഖ്യയും output ട്ട്‌പുട്ട് ദൈർഘ്യവും 0 ആയി സജ്ജമാക്കുക.
  3. അറേയിലൂടെ സഞ്ചരിക്കുക, i = 0 മുതൽ i <n വരെ.
    1. ശരിയാണെങ്കിൽ arr [i] 0 ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, തുടർന്ന് ആകെ -1 ചേർക്കുക.
    2. അല്ലെങ്കിൽ തുകയിലേക്ക് +1 ചേർക്കുക.
    3. എന്ന് പരിശോധിക്കുക തുക തുല്യമാണ് 1 ലേക്ക്, തുടർന്ന് output ട്ട്‌പുട്ട് ദൈർഘ്യത്തിന്റെ മൂല്യം 1 വർദ്ധിപ്പിക്കുക.
    4. അല്ലാത്തപക്ഷം, ഒരു മാപ്പിൽ സംഖ്യ ശരിയല്ലെങ്കിൽ പരിശോധിക്കുക, തുടർന്ന് i യുടെ ആകെത്തുകയും നിലവിലെ മൂല്യവും തുകയ്‌ക്കൊപ്പം മാപ്പിൽ ഇടുക.
    5. ഒരു മാപ്പിൽ (തുക -1) അടങ്ങിയിട്ടുണ്ടോയെന്ന് പരിശോധിക്കുക.
    6. L ട്ട്‌പുട്ട് ദൈർഘ്യം i- സൂചികയേക്കാൾ കുറവാണെങ്കിൽ (മാപ്പിലെ തുകയുടെ മൂല്യം).
      1. ശരിയാണെങ്കിൽ, l ട്ട്‌പുട്ട് ദൈർഘ്യം ഐ-സൂചികയിലേക്ക് അപ്‌ഡേറ്റുചെയ്യുക.
  4. Output ട്ട്‌പുട്ട് ദൈർഘ്യം നൽകുക.

വിശദീകരണം

ഞങ്ങൾ ഒരു പ്രഖ്യാപിക്കും ഭൂപടം. ആ മാപ്പിൽ, വ്യവസ്ഥ തൃപ്തികരമാണെങ്കിൽ, തുകയുടെ മൂല്യവും ഒരു സൂചികയുടെ നിലവിലെ മൂല്യവും ഞങ്ങൾ സംഭരിക്കാൻ പോകുന്നു. രണ്ട് വേരിയബിളുകൾ എടുത്ത് തുക 0 ഉം output ട്ട്‌പുട്ട് ദൈർഘ്യം 0 ഉം ആയി സജ്ജമാക്കുക. അറേയിലൂടെ സഞ്ചരിക്കുമ്പോൾ, ഞങ്ങൾ ഒരു അറേയുടെ ഓരോ ഘടകങ്ങളും തിരഞ്ഞെടുക്കും, കൂടാതെ arr [i] 0 ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, അത് തുല്യമാണെന്ന് കണ്ടെത്തിയാൽ, ഞങ്ങൾ ചേർക്കും -1 ആകെ തുകയായി സംഭരിക്കുക, അല്ലാത്തപക്ഷം 0 ആണെന്ന് കണ്ടെത്തിയില്ലെങ്കിൽ, ഞങ്ങൾ പോസിറ്റീവ് 1 ആകെ ചേർത്ത് സംഖ്യയായി സംഭരിക്കും.

ആ നെഗറ്റീവ് 1 നും പോസിറ്റീവ് 1 നും പിന്നിലെ കാരണം, ഞങ്ങൾ എല്ലാ 0 കളെയും -1 ലേക്ക് നടിക്കുകയും അവയെ 1 ഉപയോഗിച്ച് ചേർക്കുകയും ചെയ്യുന്നു, അതിനാൽ നമുക്ക് എല്ലായ്പ്പോഴും 0 ലഭിക്കും. എന്നാൽ പോസിറ്റീവ് 1 എന്ന് ഞങ്ങൾ പരിശോധിക്കും, ഇത് നമുക്ക് ഒരു അധിക 1 ഉണ്ടായിരിക്കുമെന്ന് സൂചിപ്പിക്കുന്നു, തുടർന്ന് 0 ന്റെ എണ്ണം.

നമ്മൾ 1, -0 എന്ന് നടിക്കുകയാണെങ്കിൽ 1, 0, 1 എടുക്കുമെന്ന് കരുതുക, ആദ്യത്തെ 0 അക്കങ്ങൾക്കൊപ്പം ആ 2 നമുക്ക് ലഭിക്കും, മൂന്നാമത്തെ നമ്പറിനൊപ്പം, നമ്മുടെ അവസ്ഥ പൂർത്തീകരിച്ചതായി നമുക്ക് കണ്ടെത്താം. 1, 0 എന്നിവയുടെ ഒരു ഉപ-അറേ ഞങ്ങൾക്ക് 1 എന്നതിനേക്കാൾ ഒരു അധിക എണ്ണം ലഭിച്ചു. ഞങ്ങളുടെ അവസ്ഥ തൃപ്‌തിപ്പെടുത്തുന്നു. അതിനാലാണ് ഒരു അൽ‌ഗോരിത്തിന്റെ അടുത്ത ഘട്ടത്തിൽ‌ തുക 0 ന് തുല്യമാണെന്നും output ട്ട്‌പുട്ടിന്റെ ദൈർ‌ഘ്യം അപ്‌ഡേറ്റുചെയ്യുമോ എന്നും ഞങ്ങൾ‌ അന്വേഷിക്കും. അവസാനത്തേതിൽ‌, സ്റ്റേറ്റ്‌മെന്റിന്, പുതിയ output ട്ട്‌പുട്ട് ദൈർ‌ഘ്യം ലഭിക്കുകയാണെങ്കിൽ‌, നിലവിലുള്ള output ട്ട്‌പുട്ട് ദൈർ‌ഘ്യം ഉപയോഗിച്ച് മുമ്പത്തെ ഒന്ന് അപ്‌ഡേറ്റ് ചെയ്യേണ്ടതുണ്ട്, മാത്രമല്ല ഞങ്ങൾ‌ output ട്ട്‌പുട്ട് ദൈർ‌ഘ്യം നൽകും.

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

ഏറ്റവും ദൈർഘ്യമേറിയ സബ്‌റേയ്‌ക്കുള്ള സി ++ പ്രോഗ്രാം 1 സെ എണ്ണമുള്ളത് 0 സെ

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

ദൈർ‌ഘ്യമേറിയ സബ്‌‌റേയ്‌ക്കുള്ള ജാവ പ്രോഗ്രാം 1 സെ. എണ്ണം 0 സെ

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

ദൈർ‌ഘ്യമേറിയ സബ്‌‌റേയ്‌ക്കുള്ള സങ്കീർ‌ണ്ണത വിശകലനം 1 സെൻറെ എണ്ണം 0 സെ

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N”  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N”  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.