मान लीजिए कि कुछ चिप्स हैं, i-th चिप वर्तमान में चिप्स की स्थिति में है[i]। हम किसी भी चिप पर (संभवतः शून्य) जितनी बार चाहें, निम्नलिखित दो प्रकार के कार्यों में से कोई भी प्रदर्शन कर सकते हैं -
-
0 की लागत से i-th चिप को 2 यूनिट से बाईं ओर या दाईं ओर ले जाएं।
-
1. की लागत से i-th चिप को 1 इकाई से बाईं ओर या दाईं ओर ले जाएं।
प्रारंभ में, दो या अधिक चिप्स हो सकते हैं। हमें सभी चिप्स को एक ही स्थिति में ले जाने के लिए आवश्यक न्यूनतम लागत वापस करनी होगी। अंतिम स्थिति कुछ भी हो सकती है। इसलिए यदि प्रारंभिक चिप की सरणी [2,2,2,3,3] है, तो आउटपुट 2 होगा। चौथी और पांचवीं दोनों चिप को लागत 1 के साथ दूसरे स्थान पर ले जाया जाएगा। तो कुल न्यूनतम लागत 2<होगी। /पी>
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
विषम:=0 और सम:=0
-
मैं के लिए 0 से लेकर सरणी की लंबाई तक
-
अगर चिप्स [i] विषम है, तो विषम बढ़ाएँ, अन्यथा सम बढ़ाएँ
-
-
कम से कम विषम और सम लौटाएं।
उदाहरण (C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int odd =0;
int even = 0;
for(int i =0;i<chips.size();i++){
if(chips[i]&1)odd++;
else even++;
}
return min(odd,even);
}
};
main(){
Solution ob;
vector<int> v1 = {2,2,2,3,3};
cout << ob.minCostToMoveChips(v1);
} इनपुट
[2,2,2,3,3]
आउटपुट
2