C++ में तीन का सबसे बड़ा गुणज

मान लीजिए कि हमारे पास अंकों की एक सरणी है, हमें तीन में से सबसे बड़ा गुणज खोजना होगा जो दिए गए अंकों में से कुछ को किसी भी क्रम में जोड़कर बनाया जा सकता है जैसा हम चाहते हैं। उत्तर बहुत बड़ा हो सकता है इसलिए इसे स्ट्रिंग के रूप में बनाएं। अगर कोई जवाब नहीं है तो एक खाली स्ट्रिंग लौटाएं।

इसलिए, अगर इनपुट [7,2,8] जैसा है, तो आउटपुट 87

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक 2D सरणी d परिभाषित करें, तीन पंक्तियाँ होंगी

• सरणी अंकों को क्रमबद्ध करें

• योग :=0

• इनिशियलाइज़ i :=0 के लिए, जब i <अंकों का आकार, अपडेट करें (i से 1 बढ़ाएँ), do−

  • एक्स:=अंक [i]

  • d[x mod 3]

    . के अंत में अंक डालें[i]

  • योग :=योग + x

  • योग :=योग मोड 3

• यदि योग शून्य नहीं है, तो -

  • यदि d[sum] का आकार नहीं है, तो -

    • रेम :=3 - योग

    • यदि d[rem] <2 का आकार है, तो -

      • खाली स्ट्रिंग लौटाएं

    • अंतिम तत्व को d[rem] से दो बार हटाएं

  • अन्यथा

    • d[sum]

      . से अंतिम तत्व हटाएं

• रिट:=खाली स्ट्रिंग

• इनिशियलाइज़ करने के लिए मैं :=0, जब i <3, अपडेट (i 1 से बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • ret :=ret concatenate d[i, j] स्ट्रिंग के रूप में

• सरणी को क्रमबद्ध करें रिट

• यदि रिट और रिट [0] का आकार '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