C++-এ সর্টেড অ্যারেতে বর্গ মান বের করে সর্ট করা

একটি সর্টেড পূর্ণসংখ্যা অ্যারে দেওয়া থাকলে, প্রতিটি উপাদানের বর্গ বের করে সেটিকে আবার সর্টেড ক্রমে প্রিন্ট করতে হবে। উদাহরণস্বরূপ,

ইনপুট-১

arr[] = {-3, -1, 0, 1, 4, 6}

আউটপুট

{0, 1, 1, 9, 16, 36}

ব্যাখ্যা

প্রদত্ত অ্যারে [-3, -1, 0, 1, 4, 6]-এর বর্গ মানগুলো হল [9, 1, 0, 1, 16, 36]। সর্ট করার পর ফলাফল [0, 1, 1, 9, 16, 36]।

ইনপুট-২

arr[] = {0, 1, 2, 8, 9}

আউটপুট

{0, 1, 4, 64, 81}

সমাধানের পদ্ধতি

এই সমস্যা সমাধানের জন্য টু-পয়েন্টার (Two-Pointer) পদ্ধতি ব্যবহার করা হয়। একটি পয়েন্টার বাম প্রান্তে (left) এবং অন্যটি ডান প্রান্তে (right) থাকে।

• অ্যারেটি ক্রমবর্ধমান ক্রমে ইনপুট নিন।
• squareAndSort(vector<int>& arr) ফাংশন বর্গ মানগুলো সর্টেড ভেক্টরে রিটার্ন করে।
• দুই পয়েন্টার left = 0 এবং right = arr.size()-1 দিয়ে শুরু করুন।
• দুই প্রান্তের বর্গ মান তুলনা করে বড়টিকে ভেক্টরে পুশ করুন এবং পয়েন্টার সরান।
• শেষে ভেক্টরটি রিভার্স করলে সর্টেড ক্রম পাওয়া যাবে।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

vector<int> squareAndSort(vector<int> &arr) {
    int left = 0;
    int right = arr.size() - 1;
    vector<int> vec;
    while (left <= right) {
        int v1 = arr[left] * arr[left];
        int v2 = arr[right] * arr[right];
        if (v1 <= v2) {
            vec.push_back(v2);
            right--;
        } else {
            vec.push_back(v1);
            left++;
        }
    }
    reverse(vec.begin(), vec.end());
    return vec;
}

int main() {
    vector<int> arr = {-3, -1, 0, 1, 4, 6};
    vector<int> ans = squareAndSort(arr);
    for (auto x : ans)
        cout << x << " ";
    return 0;
}

আউটপুট

0 1 1 9 16 36