मान लीजिए हमारे पास n तत्वों वाला एक सरणी A है। मान लें कि n धनात्मक पूर्णांकों वाला एक पासवर्ड है। हम सरणी पर निम्नलिखित संक्रियाएं लागू करते हैं। संक्रिया है दो आसन्न तत्वों को हटाना जो एक दूसरे के समान नहीं हैं, फिर उस स्थान पर उनका योग रखें। तो यह संक्रिया सरणी के आकार को 1 से कम कर देगी। हमें इन संक्रियाओं को करने के बाद सरणी की न्यूनतम संभव लंबाई ढूंढनी है।
उदाहरण के लिए, यदि इनपुट A = [2, 1, 3, 1] है, तो आउटपुट 1 होगा, क्योंकि यदि हम (1, 3) चुनते हैं, तो सरणी [2, 4, 1] होगी, फिर (2, 4) चुनकर सरणी [6, 1] बनाएं, फिर अंतिम दो को चुनकर [7] प्राप्त करें।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := size of A Define one set se for initialize i := 0, when i < n, update (increase i by 1), do: insert A[i] into se if size of se is same as 1, then: return n Otherwise return 1
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { int n = A.size(); set<int> a; for (int i = 0; i < n; i++) { a.insert(A[i]); } if (a.size() == 1) return n; else return 1; } int main() { vector<int> A = { 2, 1, 3, 1 }; cout << solve(A) << endl; }
इनपुट
{ 2, 1, 3, 1 }
आउटपुट
1