मान लीजिए हमारे पास अलग-अलग अंकों का एक ऐरे है; हमें उस सबसे बड़े 3 के गुणक को खोजना है जो उस ऐरे में दिए गए कुछ अंकों को किसी भी क्रम में जोड़कर उत्पन्न किया जा सकता है। उत्तर बहुत बड़ा हो सकता है इसलिए इसे स्ट्रिंग के रूप में बनाएं। यदि कोई उत्तर नहीं है तो खाली स्ट्रिंग लौटाएं।
उदाहरण के लिए, यदि इनपुट [7,2,8] है, तो आउटपुट 87 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- तीन पंक्तियों वाला एक 2D ऐरे d परिभाषित करें
- अंकों के ऐरे को सॉर्ट करें
- सम := 0
- i := 0 से अंकों के आकार - 1 तक लूप करें:
- x := अंक[i]
- अंक[i] को d[x % 3] के अंत में डालें
- सम := सम + x
- सम := सम % 3
- यदि शून्येतर है:
- यदि d[सम] का आकार नहीं है:
- rem := 3 - सम
- यदि d[rem] का आकार < 2, तो खाली स्ट्रिंग लौटाएं
- d[rem] से अंतिम तत्व को दो बार हटाएं
- अन्यथा d[सम] से अंतिम तत्व हटाएं
- यदि d[सम] का आकार नहीं है:
- रिट := खाली स्ट्रिंग
- i := 0 से 2 तक लूप करें:
- j := 0 से d[i] के आकार - 1 तक लूप करें: रिट := रिट + d[i][j] को स्ट्रिंग के रूप में जोड़ें
- रिट ऐरे को सॉर्ट करें
- यदि रिट का आकार और रिट[0] '0' के बराबर है, तो "0" लौटाएं
- रिट लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: string largestMultipleOfThree(vector<int>& digits) { vector<vector<int>> d(3); sort(digits.begin(), digits.end(), greater<int>()); int sum = 0; for (int i = 0; i < digits.size(); i++) { int x = digits[i]; d[x % 3].push_back(digits[i]); sum += x; sum %= 3; } if (sum) { if (!d[sum].size()) { int rem = 3 - sum; if (d[rem].size() < 2) return ""; d[rem].pop_back(); d[rem].pop_back(); } else { d[sum].pop_back(); } } string ret = ""; for (int i = 0; i < 3; i++) { for (int j = 0; j < d[i].size(); j++) { ret += to_string(d[i][j]); } } sort(ret.begin(), ret.end(), greater<int>()); if (ret.size() && ret[0] == '0') return "0"; return ret; } }; main(){ Solution ob; vector<int> v = {7,2,8}; cout << (ob.largestMultipleOfThree(v)); } इनपुट
{7,2,8} आउटपुट
87