সমস্ত জিরো প্রদত্ত অ্যারের সমাপ্তিতে সরান  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ByteDance ক্যাপিটাল ওয়ান সিসকো উপত্যকা ইবে ফেসবুক গোল্ডম্যান শ্যাস গুগল আইবিএম লিঙ্কডইন মাইক্রোসফট Nutanix আকাশবাণী পেপ্যাল Paytm কোয়ালকম স্যামসাং এসএপি ল্যাব ServiceNow Splunk টেসলা উবার ওয়ালমার্ট ল্যাব নরপশু ইয়ানডেক্স Zillow
বিন্যাস দুটি পয়েন্টার

সমস্যা বিবৃতি  

প্রদত্ত ইন বিন্যাস অ্যারেতে উপস্থিত সমস্ত শূন্যগুলি অ্যারের শেষ প্রান্তে সরান। অ্যারের শেষে সমস্ত শূন্যের সংখ্যা সন্নিবেশ করার জন্য এখানে সর্বদা একটি উপায় রয়েছে।

উদাহরণ  

ইনপুট

9

9 17 0 14 0 0 23 19 4

আউটপুট

9 17 4 14 19 23 0 0 0

সমস্ত জিরো প্রদত্ত অ্যারের শেষের দিকে সরানোর জন্য অ্যালগরিদম  

ধাপ 1: প্রদত্ত অ্যারেতে, ভেরিয়েবলের মতো দুটি পয়েন্টার নিন। বামে = 0, ডান = এন -1 (এন অ্যারের আকার) সূচনা করুন।
ক। প্রথম উপাদানটিতে বাম পয়েন্টার ভেরিয়েবল।
খ। শেষ উপাদানটিতে ডান পয়েন্টার ভেরিয়েবল।

ধাপ 2: বাম দিক থেকে এমন পথ অনুসরণ করুন যে কোনও শূন্য যদি প্রারম্ভের দিকে পাওয়া যায় এবং শেষের দিকে অ-শূন্য থাকে তবে কেবল সেগুলি সরিয়ে নিন।
ক। বাম থেকে, যদি উপাদানটি শূন্য হয় তবে এগিয়ে যান।
খ। যদি শূন্যটি পাওয়া যায় তবে ডান দিকের পয়েন্টার থেকে শূন্য অ্যালিমেন্টের দিকে পিছন থেকে ট্র্যাভার্স করুন, যদি শূন্য পাওয়া যায় তবে এটি ট্র্যাভারিং চালিয়ে যেতে পারেন।
গ। যদি শূন্য না পাওয়া যায় তবে বাম পয়েন্টারটি দিয়ে অদলবদল করুন।
d। অবশেষে, সমস্ত শূন্যগুলি অ্যারের শেষের দিকে ঠেলা যায়।

ধাপ 3: শূন্যগুলি শেষের দিকে ঠেলাঠেলি করে পরীক্ষা করতে অ্যারেটি মুদ্রণ করুন।

আরো দেখুন
এফ-বি 2-এ 1-বি 1-এ2-বি 2 হিসাবে .. 3n পূর্ণসংখ্যার স্থান পরিবর্তন করুন - .. অতিরিক্ত স্থান ব্যবহার না করে বিএন

সমস্ত জিরো প্রদত্ত অ্যারের শেষের দিকে সরানোর ব্যাখ্যা  

a [] = {9, 17, 0, 14, 0, 0, 23, 19, 4

প্রথম পদক্ষেপ: বামে 0 এবং ডানদিকে এন -1 এ।

২ য় পদক্ষেপ: আমাদের 0 টির মুখোমুখি হওয়া পর্যন্ত বাম পয়েন্টারটি বাড়ান Then তারপরে বাম = 2। এখন আমরা একটি [বাম], একটি [ডান] পরিবর্তন করব এবং বাম পয়েন্টারটি বাড়িয়ে দেব এবং ডান পয়েন্টার হ্রাস করব যা অ্যারেতে শূন্য নয় এমন উপাদানগুলি বোঝায়।

 তৃতীয় পদক্ষেপ: পরবর্তী আমরা বাম পয়েন্টার বৃদ্ধি করি যতক্ষণ না আমরা অন্য শূন্যের মুখোমুখি হই, তারপরে বাম = 4। এখন আমরা একটি [বাম], একটি [ডান] পরিবর্তন করব এবং বাম পয়েন্টারটি বাড়িয়ে দেব এবং ডান পয়েন্টার হ্রাস করব যা অ্যারেতে শূন্য নয় এমন উপাদানগুলি বোঝায়।

চতুর্থ ধাপ: এখানে আমরা ইতিমধ্যে একটি শূন্য সম্মুখীন। সুতরাং, আমরা এটি ডান পয়েন্টার অবস্থানে উপস্থিত উপাদান দিয়ে অদলবদল।

চতুর্থ ধাপ: এখন আমাদের বর্ধিত বাম পয়েন্টার পর্যন্ত কোনও শূন্যের মুখোমুখি না হওয়া পর্যন্ত incre এখন আমরা বর্ধিত এবং বাম> ডান রাখি যাতে আমরা লুপটি শেষ করি।

অতএব প্রদত্ত ইনপুটটির জন্য [9,17,0,14,0,0,23,19,4] আমাদের আউটপুট [9,17,4,14,19,23,0,0,0]।

বাস্তবায়ন  

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int left = 0 , right = N-1; // take two pointer like variables for traversal
  
  while(left < right)
  {
    if(arr[left] != 0) // if element not zero then move ahead
      left ++;
    if(arr[right] == 0) // if ending elments are zero then come backwards towards non zero elements
      right --;
      
    if(arr[left] == 0 and arr[right] != 0) // if a zero is found towards start and non zero towards end then simply swap it
        {  
        swap(arr[left++],arr[right--]);
        }
  } 
  
  for(int i = 0; i < N;i++)
    cout <<arr[i]<<" ";
  return 0;
}

জাভা প্রোগ্রাম

import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int left = 0 , right = n-1; // take two pointer like variables for traversal
        while(left < right)
        {
          if(arr[left] != 0) // if element not zero then move ahead
            left ++;
          if(arr[right] == 0) // if ending elments are zero then come backwards towards non zero elements
            right --;
          if(arr[left] == 0 && arr[right] != 0) // if a zero is found towards start and non zero towards end then simply swap it
              {  
              arr[left]=arr[left]+arr[right]-(arr[right]=arr[left]);
              left++;
              right--;
              }
        } 

        for(int i=0;i<n;i++)
          System.out.print(arr[i]+" ");
    }
}
9
9 17 0 14 0 0 23 19 4
9 17 4 14 19 23 0 0 0

সমস্ত জিরো প্রদত্ত অ্যারের শেষের দিকে নিয়ে যাওয়ার জটিলতা বিশ্লেষণ  

সময় জটিলতা

আরো দেখুন
দুটি ভারসাম্য বাইনারি অনুসন্ধান গাছগুলি মার্জ করুন

উপর) যেখানে এন অ্যারের আকার। এখানে আমরা কেবল দ্বি-পয়েন্টার ব্যবহার করি এবং তাদের মধ্যে দৈর্ঘ্য হ্রাস করতে থাকি। সুতরাং, এটি আমাদের রৈখিক সময়ের জটিলতার দিকে নিয়ে যায়।

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

ও (1) কারণ এখানে আমরা কয়েকটি পরিবর্তনশীল ব্যবহার করি যা আমাদের স্থির স্থানের জটিলতায় নিয়ে যায়।

তথ্যসূত্র