अंकों की सरणी से 3 का सबसे बड़ा गुणज ज्ञात करें - C++ में 2 सेट करें

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

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

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

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

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

• योग :=0

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

  • एक्स:=अंक [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"

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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