C++-এ অ্যাস্টেরয়েড সংঘর্ষ

একটি অ্যারে asteroids দেওয়া আছে যা একটি সারিতে অ্যাস্টেরয়েডগুলোকে বোঝায়। প্রতিটি অ্যাস্টেরয়েডের পরিমাণ তার আকার বোঝায়, আর চিহ্ন দিক বোঝায় (ধনাত্মক = ডান, ঋণাত্মক = বাম)। সব অ্যাস্টেরয়েড একই গতিতে চলে। সব সংঘর্ষের পর অ্যাস্টেরয়েডদের অবস্থা বের করতে হবে। দুটি অ্যাস্টেরয়েড মিললে ছোটটি বিফোট করবে। যদি দুটির আকার সমান হয়, দুটোই বিফোট করবে। একই দিকে যাওয়া দুটি অ্যাস্টেরয়েড কখনো মেলে না।

উদাহরণ: [5, 10, -5] হলে আউটপুট [5, 10]। এখানে ১০ আর -৫ সংঘর্ষে ১০ বাঁচে, তারপর ৫ আর ১০ কখনো মেলে না।

সমাধানের ধাপগুলো:

• ret একটা অ্যারে, n := arr.size()।
• i = 0 থেকে n-1 পর্যন্ত:
  • যদি ret খালি হয় অথবা ret-এর শেষ উপাদান ধনাত্মক আর arr[i] ঋণাত্মক হয়:
    • ret-এ arr[i] ঢোকান, i++
  • অন্যথায়:
    • x := ret-এর শেষ উপাদান, সেটি ডিলিট করুন।
    • absX := |x|, absY := |arr[i]|
    • যদি absX == absY, i++।
    • অন্যথায়:
      • যদি absX > absY, x-কে ret-এ ঢুকিয়ে i++।
• ret ফেরত দিন।

উদাহরণ (C++)

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution {    public:    bool isNeg(int x){       return x < 0;    }    vector<int> asteroidCollision(vector<int>& arr) {       vector <int> ret;       int n = arr.size();       for(int i = 0; i< n; ){          if(ret.empty() || !(!isNeg(ret[ret.size() - 1]) && isNeg(arr[i]))){             ret.push_back(arr[i]);             i++;          } else {             int x = ret[ret.size() - 1];             ret.pop_back();             int absX = abs(x);             int absY = abs(arr[i]);             if(absX == absY){                i++;             } else {                if(absX > absY){                   ret.push_back(x);                   i++;                }             }          }       }       return ret;    } }; main(){    vector<int> v = {5, 10, -4};    Solution ob;    print_vector(ob.asteroidCollision(v)); }

ইনপুট

[5,10,-4]

আউটপুট

[5, 10, ]