मान लीजिए A सरणी में N तत्व हैं। N बिल्लियाँ हैं जो 1 से N तक संख्याबद्ध हैं। प्रत्येक बिल्ली एक टोपी पहने हुए है और i-वीं बिल्ली कहती है "मेरे अलावा अन्य N-1 बिल्लियों की टोपियों में ठीक A[i] अलग-अलग रंग हैं"। हमें जाँचना है कि क्या टोपियों के रंगों का कोई अनुक्रम मौजूद है जो बिल्लियों के कथन के अनुरूप हो।
उदाहरण के लिए, यदि इनपुट है A = [1, 2, 2], तो आउटपुट True होगा, क्योंकि यदि बिल्ली 1, 2, 3 क्रमशः लाल, नीला, नीला टोपी पहनें, तो यह कथन के अनुरूप है।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
mn := अनंत, mx = 0, cnt = 0
n := A का आकार
आकार n+1 का सरणी a परिभाषित करें
i := 1 से n तक:
a[i] := A[i-1]
mn := min(mn, a[i])
mx := max(mx, a[i])
i := 1 से n तक:
यदि a[i] == mn, तो cnt बढ़ाएँ
यदि mx == mn, तो:
यदि mn == n-1 या 2*mn <= n, तो true लौटाएँ
अन्यथा false लौटाएँ
अन्यथा यदि mx == mn + 1, तो:
यदि mn >= cnt और n - cnt >= 2*(mx - cnt), तो true लौटाएँ
अन्यथा false लौटाएँ
अन्यथा false लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; bool solve(vector<int> A) { int mn = 99999, mx = 0, cnt = 0; int n = A.size(); vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { a[i] = A[i - 1]; mn = min(mn, a[i]), mx = max(mx, a[i]); } for (int i = 1; i <= n; ++i) if (a[i] == mn) ++cnt; if (mx == mn) { if (mn == n - 1 || 2 * mn <= n) return true; else return false; } else if (mx == mn + 1) { if (mn >= cnt && n - cnt >= 2 * (mx - cnt)) return true; else return false; } else return false; } int main() { vector<int> A = { 1, 2, 2 }; cout << solve(A) << endl; }
इनपुट
{ 1, 2, 2 }
आउटपुट
1
