मान लीजिए A संख्याओं की एक सूची है जिसमें N तत्व हैं। तत्व 1, 2 या 3 हैं। X[1][j] = A[j] पर विचार करें जहाँ j 1 से N की सीमा में है। और X[i][j] = |X[i-1][j] - X[i-1][j+1]| जहाँ i 2 से N की सीमा में है और j 1 से N+1-i की सीमा में है। हमें X[i][j] का मान ज्ञात करना है।
उदाहरण के लिए, यदि इनपुट है A = [1,2,3,1], तो आउटपुट 1 होगा, क्योंकि:
X[1][1] से X[1][4] हैं 1, 2, 3, 1 X[2][1], X[2][2], X[2][3] हैं |1-2|=1, |2-3|=1, |3-1|=2 X[3][1], X[3][2] हैं |1-1|=0, |1-2|=1 X[4][1] = |0-1| = 1 तो उत्तर 1 है
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक फंक्शन calc() परिभाषित करें जो N, M लेता है:
cnt := 0
k := N से जब k शून्येतर, k >>= 1:
cnt := floor((cnt + k)/2)
k := M से जब k शून्येतर, k >>= 1:
cnt := floor((cnt - k)/2)
k := N-M से जब k शून्येतर, k >>= 1:
cnt := floor((cnt - k)/2)
cnt का व्युत्क्रम लौटाएँ
मुख्य विधि से:
n := A का आकार
आकार n+1 का सरणी arr परिभाषित करें
i := 1 से n-1 तक:
arr[i-1] = |A[i] - A[i-1]|
n घटाएँ
hh := 1, pd := 0, ck := 0
i := 0 से n-1 तक:
यदि arr[i] शून्येतर है:
यदि arr[i] == 1, तो:
hh := 0
pd := pd XOR calc(n-1, i)
अन्यथा:
ck := ck XOR calc(n-1, i)
ck := ck AND hh
यदि pd XOR ck शून्येतर है, तो "1" + hh लौटाएँ
"0" लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int calc(int N, int M) { int cnt = 0; for (int k = N; k; k >>= 1) cnt += k >> 1; for (int k = M; k; k >>= 1) cnt -= k >> 1; for (int k = N - M; k; k >>= 1) cnt -= k >> 1; return !cnt; } string solve(vector<int> A) { int n = A.size(); vector<int> arr(n + 1); for (int i = 1; i < n; i++) { arr[i - 1] = abs(A[i] - A[i - 1]); } --n; bool hh = 1, pd = 0, ck = 0; for (int i = 0; i < n; i++) if (arr[i]) { if (arr[i] == 1) hh = 0, pd ^= calc(n - 1, i); else ck ^= calc(n - 1, i); } ck &= hh; if (pd ^ ck) return "1" + hh; return "0"; } int main(){ vector<int> A = { 1, 2, 3, 1 }; cout << solve(A) << endl; }
इनपुट
{ 1, 2, 3, 1 }
आउटपुट
1
