मान लीजिए A सरणी में N तत्व हैं। N बक्से हैं जो एक वृत्त में व्यवस्थित हैं। i-वें बक्से में A[i] पत्थर हैं। हमें जाँचना है कि क्या हम बार-बार ऑपरेशन करके सभी बक्सों से पत्थर हटा सकते हैं: एक बक्सा चुनें, मान लीजिए i-वाँ बक्सा। 1 से N तक प्रत्येक j के लिए, (i+j)-वें बक्से से ठीक j पत्थर हटाएँ। यहाँ (N+k)-वाँ बक्सा k-वाँ बक्सा माना जाता है। यह ऑपरेशन नहीं किया जा सकता यदि किसी बक्से में पर्याप्त पत्थर न हों।
उदाहरण के लिए, यदि इनपुट है A = [4, 5, 1, 2, 3], तो आउटपुट True होगा, क्योंकि हम दूसरे बक्से से शुरू करके सभी पत्थर हटा सकते हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
n := A का आकार
आकार n+1 के सरणी a, b परिभाषित करें
sum := 0, p := n * (n + 1) / 2
i := 1 से n तक:
a[i] := A[i-1]
sum := sum + a[i]
यदि sum % p != 0, तो false लौटाएँ
k := sum / p
i := 1 से n तक:
b[i] := a[i] - a[(i % n) + 1]
sum := 0
i := 1 से n तक:
a[i] := b[i]
sum := sum + a[i]
यदि sum != 0, तो false लौटाएँ
i := 1 से n तक:
यदि (a[i] + k) % n != 0 या a[i] + k < 0, तो false लौटाएँ
true लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; bool solve(vector<int> A) { int n = A.size(); vector<int> a(n + 1); vector<int> b(n + 1); int sum = 0, p = n * (n + 1) / 2; for (int i = 1; i <= n; i++) { a[i] = A[i - 1]; sum += a[i]; } if (sum % p != 0) { return false; } int k = sum / p; for (int i = 1; i <= n; i++) { b[i] = a[i] - a[i % n + 1]; } sum = 0; for (int i = 1; i <= n; i++) { a[i] = b[i]; sum += a[i]; } if (sum != 0) { return false; } for (int i = 1; i <= n; i++) { if ((a[i] + k) % n != 0 || a[i] + k < 0) { return false; } } return true; } int main(){ vector<int> A = { 4, 5, 1, 2, 3 }; cout << solve(A) << endl; }
इनपुट
{ 4, 5, 1, 2, 3 }
आउटपुट
1
