मान लीजिए हमारे पास एक पंक्ति में n सुपर वॉशिंग मशीन हैं। प्रारंभ में, प्रत्येक वॉशिंग मशीन में कुछ कपड़े हैं या खाली है। अब, प्रत्येक चाल के लिए, हम कोई भी m (1 ≤ m ≤ n) वॉशिंग मशीन चुन सकते हैं, और प्रत्येक वॉशिंग मशीन के एक कपड़े को उसके आसन्न वॉशिंग मशीन में एक ही समय में पास कर सकते हैं। मान लीजिए हमारे पास एक पूर्णांक ऐरे है जो बाएं से दाएं पंक्ति पर प्रत्येक वॉशिंग मशीन में कपड़ों की संख्या को दर्शाता है, हमें सभी वॉशिंग मशीनों में कपड़ों की समान संख्या बनाने के लिए न्यूनतम चालों की संख्या ज्ञात करनी चाहिए। यदि यह करना संभव नहीं है, तो -1 वापस करें।
तो जब इनपुट [1,0,5] जैसा है, तो आउटपुट 3 होगा, क्योंकि 5 को 0 पर भेजें, तो वितरण [1, 1, 4] होगा, फिर मध्य 1 को बाएं एक पर, 4 को 1 पर, तो यह [2,1,3] होगा, फिर 2 को 1 पर, तो अंत में यह [2,2,2] होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- sum := v के सभी तत्वों का योग
- n := v का आकार
- यदि sum mod n, 0 के बराबर नहीं है, तो -
- -1 वापस करें
- req := sum / n, ret := 0, extra := 0
- i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
- x := v[i]
- extra := extra + (x - req)
- ret := {ret, x - req, |extra| का अधिकतम
- ret वापस करें
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; class Solution { public: int findMinMoves(vector<int>& v) { int sum = accumulate(v.begin(), v.end(), 0); int n = v.size(); if(sum % n != 0) return -1; int req = sum / n; int ret = 0; int extra = 0; for(int i = 0; i < n; i++){ int x = v[i]; extra +=( x - req); ret = max({ret, x - req, abs(extra)}); } return ret; } }; main(){ Solution ob; vector<int> v = {2,1,6}; cout << (ob.findMinMoves(v)); }इनपुट
{2,1,6}आउटपुट
3
