Edges Not Required || Greedy Maximise XOR || C++
Intuition\n Describe your first thoughts on how to solve this problem. \nAs we can join whichever edges we like, the edges given are not required, as we can jus
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs we can join whichever edges we like, the edges given are not required, as we can just greedily choose the best values to increase the overall sum.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The min value of answer can be the sum of the given array, so we store that in the ans variable.\n2. Now we store the xor values of the elements with k in a vector of pairs. Although the 2nd entry (the element iteself) is not necessary, I did that during implementation. We also store the minimum positive difference for further usage.\n3. Then we sort the vector based on the first entry (the difference). For simple implementation, I have sorted the negative differences in the reverse order so that we can extract the least diference (i.e with the max negative value) easily.\n4. We maintain the count of the positive and negative differences.\n5. Since the positive differences are always beneficial, we add them to the ans.\n\n6. In case the count of positive differences is odd:- \n    We took one extra and has to remove it\n    Case1 : If no negative difference exist - Remove the positive  difference with the least value.\n    Case2 : Negative difference exists\n    SubCase1 : If the least neg diff (in terms of absolute value) is smaller than the min pos diff - Then we include all the pos differences and the least neg diff, as overall it results in a positive value\n    SubCase2 : If the least neg diff is larger than the min pos diff, then we cant include the min pos diff value.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n) - n is the size of values array\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) - For storing the differences\n# Code\n```\nclass Solution {\npublic:\n    static bool cmp(pair<int, int>& p1, pair<int, int>& p2) {\n        if (p1.first < 0 and p2.first < 0) return p2.first > p1.first;\n        return p1 > p2;\n    }\n    long long maximumValueSum(vector<int>& v, int k,\n                              vector<vector<int>>& edges) {\n        vector<pair<int, int>> xors;\n        int mn = INT_MAX;\n        for (auto& i : v) {\n            xors.push_back({(i ^ k) - i, (i ^ k)});\n            if ((i ^ k) - i > 0) mn = min(mn, (i ^ k) - i);\n        }\n        sort(xors.begin(), xors.end(), cmp);\n        long long ans = accumulate(v.begin(), v.end(), 0ll);\n        int ct1 = 0, ct2 = 0;\n        for (int i = 0; i < v.size(); i++) {\n            if ((v[i] ^ k) > v[i])\n                ct1++;\n            else\n                ct2++;\n        }\n        for (int i = 0; i < xors.size() and xors[i].first > 0; i++)\n             ans += xors[i].first;\n        if (ct1 & 1) {\n            if (ct2 == 0) {\n                ans -= mn;\n            } \n            else {\n                if (mn - abs(xors.back().first) >= 0) {\n                    ans -= (-1 * xors.back().first);\n                } \n                else {\n                    ans -= mn;\n                }\n            }\n        }\n        return ans;\n    }\n    \n};\n```
['Greedy', 'C++']