দীর্ঘতম সুব্রেরিতে 1 এর গণনার চেয়ে 0 এসের বেশি গণনা রয়েছে  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় Accenture মর্দানী স্ত্রীলোক ডিই শ স্যামসাং
বিন্যাস কাটা

আমরা একটি দিয়েছি বিন্যাস পূর্ণসংখ্যার একটি অ্যারেতে কেবল 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 From, দুটি 1 এবং একটি 0 রয়েছে। 1 এর চেয়ে 0 এর আরও একটি গণনা।

অ্যালগরিদম  

  1. একটি মানচিত্র ঘোষণা করুন।
  2. যোগফল এবং আউটপুট দৈর্ঘ্য 0 তে সেট করুন।
  3. অ্যারেটি অতিক্রম করুন, যখন আমি = 0 থেকে আই <এন।
    1. আরে [i] 0 এর সমান কিনা তা পরীক্ষা করে যোগফল -1 যোগ করুন।
    2. অন্যটি যোগ করতে +1 যোগ করুন।
    3. পরীক্ষা করে দেখুন সমষ্টি সমান 1 এ, তারপরে আউটপুট দৈর্ঘ্যের মান 1 দ্বারা বাড়ান।
    4. অন্যথায়, মানচিত্রে যোগফলটি সঠিক না থাকে কিনা তা পরীক্ষা করুন এবং তারপরে i এর যোগফল এবং বর্তমান মান যোগফলের সাথে মানচিত্রে রেখে দিন।
    5. কোনও মানচিত্রে (যোগ -1) রয়েছে কিনা তা পরীক্ষা করুন।
    6. যদি আউটপুটলেন্থ আই-ইনডেক্সের চেয়ে কম হয় (মানচিত্রে যোগফলের মান)।
      1. যদি সত্য হয়, তবে আউটপুট দৈর্ঘ্যটিকে আই-সূচীতে আপডেট করুন।
  4. রিটার্ন আউটপুট দৈর্ঘ্য।
আরো দেখুন
এম পরিসীমা টগল অপারেশনের পরে বাইনারি অ্যারে

ব্যাখ্যা  

আমরা একটি ঘোষণা করব মানচিত্র। সেই মানচিত্রে, শর্তটি সন্তুষ্ট হলে আমরা যোগফলের মান এবং একটি সূচকের বর্তমান মান সংরক্ষণ করতে যাচ্ছি। দুটি ভেরিয়েবল নিন এবং যোগফল 0 এবং আউটপুট দৈর্ঘ্য 0 এ সেট করুন, অ্যারেটি ট্র্যাভার করার সময় আমরা একটি অ্যারের প্রতিটি উপাদান বাছাই করব, এবং এটি পরীক্ষা করব যদি অ্যারে [i] 0 এর সমান হয় তবে এটি সমান হলে আমরা যোগ করব এটির যোগফল করতে এবং এটির যোগফল সংরক্ষণ করতে হবে, অন্যথায় যদি আমরা 1 হিসাবে খুঁজে না পেয়ে থাকেন তবে আমরা যোগফলের জন্য ইতিবাচক 0 যোগ করব এবং এটির যোগফল করব।

Negativeণাত্মক 1 এবং ধনাত্মক 1 এর পিছনে কারণটি হ'ল, আমরা সমস্ত 0 এর থেকে -1 এর ভান করছি এবং এগুলিকে 1 দিয়ে যুক্ত করছি, তাই আমরা সর্বদা 0 পাব। তবে আমরা যোগফলের জন্য ইতিবাচক 1 টি যাচাই করব, যা সূচিত করে যে আমাদের আরও 1 হবে তারপর 0 এর গণনা।

ধরা যাক, আমরা 1 হিসাবে -0 হিসাবে ভান দিলে আমরা 1, 0, 1 নেব, আমরা প্রথম 0 সংখ্যার সাথে 2টি পেয়ে যাব এবং তৃতীয় নম্বর সহ আমরা দেখতে পেলাম যে আমাদের শর্তটি পূরণ হয়েছে। আমরা 1 এর চেয়ে 0 টির অতিরিক্ত অতিরিক্ত গণনা সহ 1 এবং 0 এর উপ-অ্যারে পেয়েছি our এই কারণেই আমরা সন্ধান করব যে কোনও অ্যালগরিদমের পরবর্তী ধাপে যোগফল 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 এসের বেশি গণনা রয়েছে  

সময় জটিলতা

উপর) কোথায় "এন"  অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

উপর) কোথায় "এন"  অ্যারেতে উপাদানগুলির সংখ্যা।