मान लीजिए हमारे पास n तत्वों वाला एक सरणी A है। मान लें कि एक पंक्ति में n ब्लॉक टावर हैं। i-वें टावर की ऊंचाई A[i] है। एक दिन में, हम संक्रिया कर सकते हैं: दो सूचकांक i और j चुनें (i != j) और टावर i से j में वापस ले जाएं। यह A[i] को 1 से घटा देगा और A[j] को 1 से बढ़ा देगा। इमारतों की कुरूपता max(A) - min(A) है। हमें न्यूनतम संभव कुरूपता ढूंढनी है जिसे हम प्राप्त कर सकते हैं।
उदाहरण के लिए, यदि इनपुट A = [1, 2, 3, 1, 5] है, तो आउटपुट 1 होगा, क्योंकि हम i=2 और j=0 के लिए तीन संक्रियाएं कर सकते हैं, नई सरणी अब [2,2,2,1,5] होगी, फिर i = 4 और j = 3 के लिए, सरणी [2,2,2,2,4] होगी, और i = 4 और j = 2 के लिए, सरणी [2,2,3,2,3] होगी।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
sum := 0 x := 0 n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: sum := sum + A[i] if sum mod n is same as 0, then: return 0 return 1
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { int sum = 0, x = 0; int n = A.size(); for (int i = 0; i < n; i++) sum += A[i]; if (sum % n == 0) return 0; return 1; } int main() { vector<int> A = { 1, 2, 3, 1, 5 }; cout << solve(A) << endl; }
इनपुट
{ 1, 2, 3, 1, 5 }
आउटपुट
1
