मान लीजिए N के कुछ निश्चित मान के लिए, एक ऐरे A सुंदर (beautiful) होता है जब यह 1, 2, ..., N पूर्णांकों का एक क्रमचय होता है, जैसे कि:
प्रत्येक i < j के लिए, ऐसा कोई k नहीं होता जहां i < k < j और A[k] * 2 = A[i] + A[j]।
हमें N दिया गया है, हमें कोई भी सुंदर ऐरे A खोजना है।
उदाहरण के लिए, यदि इनपुट 5 है, तो आउटपुट [3,1,2,5,4] होगा।
समाधान दृष्टिकोण
ret ऐरे बनाएं, 1 डालें
जब तक ret का आकार < N:
temp ऐरे बनाएं
पहले विषम संख्याएं: ret[i]*2-1 ≤ N होने पर जोड़ें
फिर सम संख्याएं: ret[i]*2 ≤ N होने पर जोड़ें
ret := temp सेट करें
ret लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> 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;
}
};
int main(){
Solution ob;
print_vector(ob.beautifulArray(6));
return 0;
}
इनपुट
5
आउटपुट
[1,5,3,2,4]