समस्या
मान लीजिए एक प्रारंभिक सरणी arr है, प्रत्येक दिन हम पिछले दिन की सरणी का उपयोग करके एक नई सरणी उत्पन्न करते हैं। i-वें दिन, हम दिन i-1 की सरणी पर निम्नलिखित संक्रियाएँ करके दिन i की सरणी उत्पन्न करेंगे। शर्तें इस प्रकार हैं:
- यदि कोई तत्व अपने बाएँ और दाएँ आसन्न मानों दोनों से छोटा है, तो इस तत्व को बढ़ाया जाता है।
- यदि कोई तत्व अपने बाएँ और दाएँ आसन्न मानों दोनों से बड़ा है, तो इस तत्व को घटाया जाता है।
- पहला और अंतिम तत्व समान रहेंगे।
कुछ दिनों के बाद, सरणी में कोई परिवर्तन नहीं होता। वह अंतिम सरणी ढूंढें। उदाहरण के लिए, यदि प्रारंभिक सरणी [6,2,3,4] है तो आउटपुट [6,3,3,4] होगा। पहले दिन, सरणी [6,2,3,4] से [6,3,3,4] में बदल जाएगी, फिर कोई और संक्रिया नहीं की जाएगी।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- यदि सरणी का आकार 2 या उससे कम है, तो सरणी लौटाएं
- flag := true सेट करें
- जब तक flag true है
- flag := false सेट करें
- एक खाली सरणी temp बनाएं, और arr[0] को temp में डालें
- i को 1 से सरणी आकार - 1 तक लूप में
- यदि arr[i] < arr[i-1] और arr[i] < arr[i+1], तो arr[i]+1 को temp में डालें, और flag को true सेट करें
- अन्यथा यदि arr[i] > arr[i-1] और arr[i] > arr[i+1], तो arr[i]-1 को temp में डालें, और flag := true सेट करें
- अन्यथा arr[i] को temp में डालें
- arr के अंतिम तत्व को temp में डालें
- arr := temp
- arr लौटाएं
उदाहरण (C++):
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; #define push push_back 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> transformArray(vector<int>& arr) { if(arr.size()<=2)return arr; bool flag = true; while(flag){ flag = false; vector <int> temp; temp.push_back(arr[0]); for(int i = 1; i < arr.size()-1; i++){ if(arr[i]< arr[i-1] && arr[i]<arr[i+1]){ temp.push(arr[i]+1); flag = true; } else if(arr[i]> arr[i-1] && arr[i]>arr[i+1]){ flag = true; temp.push(arr[i]-1); } else temp.push(arr[i]); } temp.push_back(arr[arr.size()-1]); arr = temp; } return arr; } }; main(){ Solution ob; vector<int> v = {1,6,3,4,3,5}; print_vector(ob.transformArray(v)); }इनपुट
[1,6,3,4,3,5]
आउटपुट
[1,4,4,4,4,5]