मान लीजिए कुछ चिप्स हैं, i-वीं चिप वर्तमान में स्थिति chips[i] पर है। हम निम्न दो प्रकार के ऑपरेशन्स में से किसी को भी जितनी बार चाहें (संभवतः शून्य) किसी भी चिप पर कर सकते हैं -
i-वीं चिप को 2 यूनिट बाएं या दाएं 0 लागत पर ले जाएं।
i-वीं चिप को 1 यूनिट बाएं या दाएं 1 लागत पर ले जाएं।
प्रारंभ में, दो या अधिक चिप्स हो सकते हैं। हमें सभी चिप्स को उसी स्थिति में ले जाने के लिए आवश्यक न्यूनतम लागत लौटानी है। अंतिम स्थिति कुछ भी हो सकती है। तो यदि प्रारंभिक चिप्स की सरणी [2,2,2,3,3] है, तो आउटपुट 2 होगा। चौथी और पांचवीं चिप दोनों को लागत 1 के साथ स्थिति दो पर ले जाया जाएगा। तो कुल न्यूनतम लागत 2 होगी।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
odd := 0 और even := 0
i को 0 से सरणी की लंबाई तक की रेंज में
यदि chips[i] विषम है, तो odd बढ़ाएं, अन्यथा even बढ़ाएं
odd और even का न्यूनतम लौटाएं।
उदाहरण (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