সি++-এ বিউটিফুল অ্যারে (Beautiful Array)

কোনো নির্দিষ্ট N-এর জন্য, একটি অ্যারে A beautiful বলা হয় যদি এটি ১, ২, ..., N পূর্ণসংখ্যাগুলোর একটি পারমুটেশন হয়, যাতে -

প্রতিটি i < j-এর জন্য, i < k < j এমন কোনো k নেই যাতে A[k] * 2 = A[i] + A[j]。

N দেওয়া থাকলে, যেকোনো একটি beautiful array A খুঁজে বের করতে হবে। ইনপুট ৫ হলে আউটপুট [3,1,2,5,4]।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -

ret নামে একটি অ্যারে তৈরি করুন, ১ ইনসার্ট করুন
যখন ret.size() < N
- temp নামে একটি অ্যারে তৈরি করুন
- i = 0 থেকে ret.size()-1 পর্যন্ত লুপ চালান
  - যদি ret[i] * 2 - 1 <= N হয়, temp-এ ret[i] * 2 - 1 ইনসার্ট করুন
- i = 0 থেকে ret.size()-1 পর্যন্ত লুপ চালান
  - যদি ret[i] * 2 <= N হয়, temp-এ ret[i] * 2 ইনসার্ট করুন
- ret := temp সেট করুন
ret রিটার্ন করুন

নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -

উদাহরণ

#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:    vector<int> beautifulArray(int N) {       vector <int> ret;       ret.push_back(1);       while(ret.size() < N){          vector <int> temp;          for(int i = 0; i < ret.size(); i++){             if(ret[i] * 2 - 1 <= N) temp.push_back(ret[i] * 2 - 1);          }          for(int i = 0; i < ret.size(); i++){             if(ret[i] * 2 <= N)temp.push_back(ret[i] * 2 );          }          ret = temp;       }       return ret;    } }; main(){    Solution ob;    print_vector(ob.beautifulArray(6)); }

ইনপুট

আউটপুট

[1,5,3,2,4]