1s ની ગણતરી કરતાં 0s એકની ગણતરી સૌથી લાંબી સુબરે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર એમેઝોન ડીઇ શw સેમસંગ
અરે હેશ

અમે એક આપ્યો છે એરે પૂર્ણાંકોની. એરેમાં ફક્ત 1 અને 0 જ હોય ​​છે. સમસ્યાનું નિવેદન સૌથી લાંબી પેટા એરેની લંબાઈ શોધવા માટે પૂછે છે જેમાં 1 અંકનો જથ્થો ધરાવતા પેટા-એરેમાં 0 ની ગણતરી કરતા માત્ર એક વધુ છે.

ઉદાહરણ

ઇનપુટ:

એરે [] = {1,0,1,1,0,0,0}

આઉટપુટ:

5

સમજૂતી:

0 થી 4 અનુક્રમણિકા, {1, 0, 1, 1, 0}, ત્યાં ત્રણ છે 1 અને બે 0's. 1 કરતા 0 ની માત્ર એક વધુ ગણતરી.

ઇનપુટ:

એરે [] = {1,0,1,0,0}

આઉટપુટ:

3

સમજૂતી:

0 થી 2 અનુક્રમણિકા, {1, 0, 1}, ત્યાં બે 1 અને એક 0 છે. 1 કરતા 0 ની માત્ર એક વધુ ગણતરી.

અલ્ગોરિધમ

  1. નકશો જાહેર કરો.
  2. સરવાળો અને આઉટપુટ લંબાઈને 0 પર સેટ કરો.
  3. એરેને પસાર કરો, જ્યારે i = 0 થી i <n.
    1. ચકાસો કે શું એઆર [i] બરાબર છે જો સાચું હોય તો સરવાળો -0 ઉમેરો.
    2. બાકી સરવાળોમાં +1 ઉમેરો.
    3. જો તપાસો સરવાળો બરાબર છે 1 થી કરો, પછી આઉટપુટ લંબાઈનું મૂલ્ય 1 દ્વારા વધારવું.
    4. બાકી, તપાસો કે જો નકશામાં સરવાળો નથી કે કેમ તે સાચું છે, તો સરવાળો સાથે નકશા પર i નો સરવાળો અને વર્તમાન મૂલ્ય મૂકો.
    5. નકશામાં (સરવાળો -1) છે કે કેમ તે તપાસો.
    6. જો આઉટપુટ લંબાઈ આઇ-ઇન્ડેક્સ (નકશામાં સરવાળો મૂલ્ય) કરતા ઓછી હોય.
      1. જો સાચું હોય, તો પછી આઉટપુટની લંબાઈને આઇ-ઇન્ડેક્સમાં અપડેટ કરો.
  4. રીટર્ન આઉટપુટ લંબાઈ.

સમજૂતી

અમે જાહેર કરીશું a નકશો. જો તે નકશામાં, જો સ્થિતિ સંતોષશે તો, આપણે સરવાળાનું મૂલ્ય અને અનુક્રમણિકાનું વર્તમાન મૂલ્ય સંગ્રહિત કરીશું. બે ચલો લો અને સરવાળો 0 અને આઉટપુટની લંબાઈ 0 થી સેટ કરો, જ્યારે એરેને ટ્રingવર્સ કરતી વખતે, આપણે એરેના દરેક ઘટકને પસંદ કરીશું, અને તપાસશે કે જો એરે [i] બરાબર છે, જો તે બરાબર છે, તો અમે ઉમેરીશું. -0 નો સરવાળો કરવા અને તેને સરવાળો કરવા માટે સંગ્રહિત કરો, અન્યથા જો આપણને 1 મળ્યા નથી, તો આપણે સારામાં સકારાત્મક 0 ઉમેરીશું અને તેને સરવાળોમાં સ્ટોર કરીશું.

તે નકારાત્મક 1 અને સકારાત્મક 1 પાછળનું કારણ છે, આપણે બધા 0 ના -1 નો ડોળ કરીએ છીએ અને તેમને 1 સાથે ઉમેરીએ છીએ, તેથી આપણને 0 હંમેશા મળશે. પરંતુ આપણે સરવાળે હકારાત્મક 1 ની તપાસ કરીશું, જે દર્શાવે છે કે આપણી પાસે એક વધારાનું 1 હશે પછી 0 ની ગણતરી.

ધારો કે, આપણે 1, 0, 1 લઈશું જો આપણે 0 તરીકે -1 બતાવીએ છીએ, તો આપણે તે 0 પ્રથમ 2 નંબરો સાથે મેળવીશું, અને ત્રીજા નંબર સાથે, આપણે શોધી શકીએ કે આપણી શરત પૂરી થઈ છે. આપણને 1 થી 0 ની વધારાની ગણતરી સાથે 1 અને 0 ની પેટા-એરે મળી છે. આપણી સ્થિતિને સંતોષ થાય છે. તેથી જ અમે શોધીશું કે જો અલ્ગોરિધમનોના આગલા પગલામાં સરવાળો 1 ની બરાબર છે અને આઉટપુટ લંબાઈની લંબાઈને અપડેટ કરીશું. છેલ્લામાં, જો નિવેદન, જો આપણને નવી આઉટપુટ લંબાઈ મળે, તો આપણે વર્તમાન આઉટપુટ લંબાઈ સાથે પાછલી એકને અપડેટ કરવાની જરૂર છે અને આપણે આઉટપુટ લંબાઈ પરત કરીશું.

અમલીકરણ

લાંબી સુબેરે માટે સી ++ પ્રોગ્રામ 1s ની ગણતરી કરતા વધુ 0s ની ગણતરી છે

#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

લાંબી સુબેરે માટે જાવા પ્રોગ્રામ 1s ની ગણતરી કરતા વધુ 0s ની ગણતરી છે

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

1s ની ગણતરી 0s ની ગણતરી કરતા વધુ લાંબી સુબરે માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન”  એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન”  એરેમાં તત્વોની સંખ્યા છે.