সংক্ষিপ্ত অ্যারে


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক MakeMyTrip মরগ্যান স্ট্যানলি Paytm
হ্যাশ সহচরী উইন্ডোতে

দেওয়া হয়েছে একটি বিন্যাস কেবল 0 এবং 1 এর সংখ্যা নিয়ে গঠিত। আমাদের ও এর সমান সমান সমন্বিত দীর্ঘতম সংযুক্ত সাব-অ্যারের দৈর্ঘ্যটি খুঁজে পেতে হবে।

উদাহরণ

ইনপুট

অ্যারে = [0,1,0,1,0,0,1]

আউটপুট

6

ব্যাখ্যা

দীর্ঘতম সংযুক্ত উপ-অ্যারে লাল চিহ্নযুক্ত [0,1,0,1,0,0,1] এবং এর দৈর্ঘ্য 6।

অ্যালগরিদম

  1. ম্যাক্সলেনের মান 0 তে নির্ধারণ করুন।
  2. দুটি লুপ ব্যবহার করুন, প্রথম লুপে 0 টি জির_কাউন্ট সেট করুন, এক_কাউন্ট থেকে 0।
  3. যদি মান হয় একটি নির্দিষ্ট সূচীতে অ্যারে 0 বলে পাওয়া গেছে তখন শূন্য_কাউন্টকে 1 দ্বারা বাড়িয়ে দিন।
  4. অন্য আপডেট এবং ওয়ান অ্যাকাউন্টকে 1 দ্বারা বাড়িয়ে দিন।
  5. প্রতিটি পুনরাবৃত্তিতে শূন্য_কাউন্ট এক_কাউন্টের সমান, যদি সমান হয় তা পরীক্ষা করুন, তারপরে বৃহত্তর সংখ্যাটি সন্ধান করুন (ম্যাক্লেলেন এবং জে-আই + 1)
  6. রিটার্ন ম্যাক্সেলেন

ব্যাখ্যা

আমাদের মূল ধারণাটি দীর্ঘতম সুসংগত সাববারেটির দৈর্ঘ্য সন্ধান করা যা শূন্য এবং তার একমাত্র, তাই আমাদের দৈর্ঘ্যটি সন্ধান করা আমাদের মূল ফোকাস।

সুতরাং, আমরা লুপ জন্য নেস্টেড ব্যবহার করতে যাচ্ছি। বাইরের লুপে, আমরা শূন্য_কাউন্ট এবং ওয়ান_কাউন্টের মান 0 দিয়ে শুরু করি কারণ প্রতিটি পুনরাবৃত্তির পরে যখন এটি অভ্যন্তরীণ লুপ থেকে বেরিয়ে আসে তখন আমাদের আবার নতুন করে পরীক্ষা করার জন্য শূন্য_কাউন্ট এবং ওয়ান_কাউন্টের নতুন মান প্রয়োজন need অ্যারের দৈর্ঘ্য না হওয়া পর্যন্ত আমরা লুপ ধরে পুনরাবৃত্তি করতে যাচ্ছি।

এখন এটি অ্যারের প্রতিটি একক মান যাচাই করতে চলেছে, যদি এরর [সূচক] এর মান 0 বা 1 থাকে তবে এর মান 0 থাকে তবে তার পরে আপডেট করে শূন্য_কাউন্টের মান 1 বা বাড়িয়ে দিলে [সূচক] 1 হিসাবে পাওয়া গেছে, তারপরে এটি আপডেট হয়ে ওয়ান_কাউন্টের মান 1 করে বাড়ায়।

এখন, পরবর্তী যদি ব্লকটি শূন্য_কাউন্ট এক_কাউন্টের সমান কিনা তা পরীক্ষা করতে চলেছে, যদি সমান হয়, তবে ম্যাক্সলেন এবং জে-আই + 1 এর মধ্যে বড় সংখ্যাটি খুঁজে বের করুন এবং ম্যাক্সলেলেনে বড় সংখ্যাটি সঞ্চয় করে রাখুন।

উদাহরণ

ধরুন অ্যারে দেওয়া হয়েছে: আরার [] = {1,0,0,1,0,1,0}

শূন্য_কাউন্ট = 0, এক_কাউন্ট = 0, ম্যাক্সেলেন = 0

i = 0, => j = i এ

j = 0

আরে [জে] 0 এর সমান নয়, তারপরে এক_কাউন্ট ++, মানে এক_কাউন্ট = 1

j = 1

আরে [জে] 0 এর সমান, তারপরে শূন্য_কাউন্ট ++, মানে শূন্য_কাউন্ট = 1

এই জায়গায় যদি ব্লক কার্যকর করা হয় তবে এটি ম্যাক্সলেন এবং j-i + 1 এর মধ্যে বড় কিছু দেয় না এবং ম্যাকলেলেনে 2 ফেরত দেয়

j = 2

আরে [জে] 0 এর সমান, তারপরে শূন্য_কাউন্ট ++, মানে শূন্য_কাউন্ট = 2

j = 3

আরে [জে] 0 এর সমান নয়, তারপরে এক_কাউন্ট ++, মানে এক_কাউন্ট = 2

এই জায়গায় যদি ব্লক কার্যকর করা হয় তবে এটি ম্যাক্সলেন এবং j-i + 1 এর মধ্যে বড় কিছু দেয় না এবং ম্যাক্সলেলেনে 4 প্রদান করে।

j = 4

আরে [জে] 0 এর সমান, তারপরে শূন্য_কাউন্ট ++, মানে শূন্য_কাউন্ট = 3

j = 5

আরে [জে] 0 এর সমান নয়, তারপরে এক_কাউন্ট ++, মানে এক_কাউন্ট = 3

এই জায়গায় যদি ব্লক কার্যকর করা হয় তবে এটি ম্যাক্সলেন এবং j-i + 1 এর মধ্যে বড় কিছু দেয় না এবং ম্যাক্সলেলেনে 6 প্রদান করে।

j = 6

আরে [জে] 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

সংক্ষিপ্ত অ্যারে জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * এন) কোথায় N প্রদত্ত অ্যারের আকার।

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

ও (1) কারণ আমরা এখানে কোনও অতিরিক্ত স্থান ব্যবহার করি না।

উল্লেখ