मान लीजिए हमारे पास n संख्या के तत्वों के साथ दो सरणी A और B हैं। एक ऑपरेशन पर विचार करें: दो इंडेक्स i और j चुनें, फिर iवें तत्व को 1 से घटाएं और jवें तत्व को 1 से बढ़ाएं। ऑपरेशन करने के बाद सरणी का प्रत्येक तत्व गैर-नकारात्मक होना चाहिए। हम A और B को समान बनाना चाहते हैं। हमें A और B को समान बनाने के लिए ऑपरेशन का क्रम ढूंढना है। यदि संभव नहीं है, तो -1 वापस करें।
उदाहरण के लिए, यदि इनपुट A = [1, 2, 3, 4]; B = [3, 1, 2, 4] है, तो आउटपुट [(1, 0), (2, 0)] होगा, क्योंकि i = 1 और j = 0 के लिए सरणी [2, 1, 3, 4] होगी, फिर i = 2 और j = 0 के लिए, यह [3, 1, 2, 4] होगी।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
a := 0, b := 0, c := 0 n := size of A Define an array C of size n and fill with 0 for initialize i := 0, when i < n, update (increase i by 1), do: a := a + A[i] for initialize i := 0, when i < n, update (increase i by 1), do: b := b + A[i] if a is not equal to b, then: return -1 Otherwise for initialize i := 0, when i < n, update (increase i by 1), do: c := c + |A[i] - B[i]| C[i] := A[i] - B[i] c := c / 2 i := 0 j := 0 while c is non-zero, decrease c after each iteration, do: while C[i] <= 0, do: (increase i by 1) while C[j] >= 0, do: (increase j by 1) print i and j decrease C[i] and increase C[j] by 1
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; void solve(vector A, vector B){ int a = 0, b = 0, c = 0; int n = A.size(); vector C(n, 0); for (int i = 0; i < n; i++) a += A[i]; for (int i = 0; i < n; i++) b += A[i]; if (a != b){ cout << -1; return; } else{ for (int i = 0; i < n; i++){ c += abs(A[i] - B[i]); C[i] = A[i] - B[i]; } c = c / 2; int i = 0, j = 0; while (c--){ while (C[i] <= 0) i++; while (C[j] >= 0) j++; cout << "(" << i << ", " << j << "), "; C[i]--, C[j]++; } } } int main(){ vector A = { 1, 2, 3, 4 }; vector B = { 3, 1, 2, 4 }; solve(A, B); }
इनपुट
{ 1, 2, 3, 4 }, { 3, 1, 2, 4 }आउटपुट
(1, 0), (2, 0),