सर्वात प्रदीर्घ सबरी ज्या 1 च्या संख्येपेक्षा 0 एस जास्त आहेत  


अडचण पातळी सोपे
वारंवार विचारले ऐक्सचर ऍमेझॉन डीई शॉ सॅमसंग
अरे हॅश

आम्ही एक दिले आहे अॅरे पूर्णांक अ‍ॅरेमध्ये केवळ 1 आणि 0 चे असतात. प्रॉब्लेम स्टेटमेंटमध्ये सर्वात लांब उप-अ‍ॅरेची लांबी शोधण्यास सांगितले जाते ज्यामध्ये 1 च्या अंकीचे प्रमाण उप-अ‍ॅरेमधील 0 च्या मोजण्यापेक्षा फक्त एक जास्त असते.

उदाहरण  

इनपुट:

अरे [] = {1,0,1,1,0,0,0}

आउटपुट:

5

स्पष्टीकरण:

0 ते 4 निर्देशांक, {1, 0, 1, 1, 0} असे तीन आहेत 1 आणि दोन 0 चे. 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] बरोबर असल्यास ० बरोबर असल्यास तपासा-बेरीज करण्यासाठी -१ जोडा.
    2. अन्यथा +1 जोडा.
    3. ते तपासा बेरीज समान आहे 1 वर जा, नंतर आउटपुटलांबीचे मूल्य 1 ने वाढवा.
    4. अन्यथा, नकाशामध्ये बेरीज बरोबर नसल्यास हे तपासा, तर i ची बेरीज आणि वर्तमान मूल्य बेरीजसह नकाशावर ठेवा.
    5. नकाशामध्ये (बेरीज -1) समाविष्ट आहे का ते तपासा.
    6. जर आउटपुटची लांबी आय-अनुक्रमणिकेपेक्षा कमी असेल (नकाशामधील बेरीजचे मूल्य).
      1. सत्य असल्यास, आऊटपुटलांबी आय-अनुक्रमणिकेत अद्यतनित करा.
  4. रिटर्न आउटपुट लांबी.
हे सुद्धा पहा
एम श्रेणी टॉगल ऑपरेशन्स नंतर बायनरी अ‍ॅरे

स्पष्टीकरण  

आम्ही घोषित करू नकाशा. त्या नकाशामध्ये, अट पूर्ण झाल्यास आम्ही बेरीजचे मूल्य आणि निर्देशांकाचे सध्याचे मूल्य संग्रहित करणार आहोत. दोन व्हेरिएबल्स घ्या आणि 0 आणि आउटपुटची लांबी 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 च्या उप-अ‍ॅरे मिळाली. आम्ही आमच्या अट पूर्ण करतो. म्हणूनच आम्ही अल्गोरिदमच्या पुढील चरणात बेरीज 1 समान असल्याचे शोधत आहोत आणि आउटपुटलॅन्थची लांबी अद्यतनित करत आहोत. शेवटी, जर स्टेटमेंट, जर आपल्याला नवीन आउटपुट लांबी मिळाली तर आपल्याला मागील आउटपुटला वर्तमान आउटपुटलेंथसह अद्यतनित करणे आवश्यक आहे आणि आपण आउटपुटलेंथ परत करू.

हे सुद्धा पहा
डुप्लिकेट घटक शोधा

अंमलबजावणी  

प्रदीर्घ सुबरीसाठी सी ++ प्रोग्राम 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) जेथे “एन”  अ‍ॅरे मधील घटकांची संख्या.

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

O (n) जेथे “एन”  अ‍ॅरे मधील घटकांची संख्या.