/* [Challenge] Maximum Sum Input: n number of integers Output: maximum sum of inputs provided You have to find maximum sum of inputs provided, You can't add numbers which has common digit in number. Test case : 10,25,46,56 Output: 10+25+46=81 In above test case 25,56 --> 5 is common and in 46,56--> 6 is common so 56 is discarded Input can have number which has more than 3 digits. Originally posted as a Q&A question, which was mfd, by Chandrakant More: https://www.sololearn.com/Profile/2848982 https://www.sololearn.com/Discuss/1829430 https://www.sololearn.com/post/108608/?ref=app Could not think of a better algorithm. */ #include #include #include #include using namespace std; class Maxsum { public: void get_max_sum(vector const &numset) { gen_power_list(numset); // the max sum is in the last // element of the map. cout << "Sum : " << prev(unq_lst.end())->first << ",[ "; for (auto const &lst : (prev(unq_lst.end())->second)) { cout << lst << " "; } cout << "]\n"; } private: void gen_power_list(vector const &numset) { // generate powerset from the input // number list size_t set_size = 1 << numset.size(); // intermediate list list pw_lst; for (size_t id=0; id &lst) { int sum{0}; for (auto it=lst.begin(); it != lst.end(); ++it) { int q = *it / 10; int r = *it % 10; sum += *it; for (auto iti=next(it); iti != lst.end(); ++iti) { int qtc = *iti / 10; int rtc = *iti % 10; if (q == qtc || r == qtc || q == rtc || r == rtc) { // at least one digit is // common among numbers so // skip it. return; } } // end inner for } // end outer for // if you are here it means the // intermediate list has all // numbers with unique digits. So // add the list to the map with // sum as the key unq_lst[sum] = lst; } map> unq_lst; }; int main() { Maxsum msum; vector numset {10, 23, 32, 34, 35, 45, 50, 76, 89}; msum.get_max_sum(numset); return 0; }

[Challenge]Maximum_sum.cpp