Greedy Approach O(N) Solution || C++ 🔥💯
Maximum Value Sum\n\n## Problem Statement\n\nGiven a tree represented by nums and edges, and an integer k, we need to maximize the sum of the values in nums aft
# Maximum Value Sum\n\n## Problem Statement\n\nGiven a tree represented by `nums` and `edges`, and an integer `k`, we need to maximize the sum of the values in `nums` after potentially transforming each value using the bitwise XOR operation with `k`. Specifically, for each value `num` in `nums`, we can either leave it as is or transform it to `num ^ k`.\n\n## Approach\n\n### Initial Calculation\n- Iterate through the given `nums` array to compute the initial sum. For each number in `nums`, calculate the maximum value between the number itself and its bitwise XOR with `k` (`num ^ k`). Add this maximum value to the sum.\n- Simultaneously, keep track of the count of numbers where `num ^ k` is greater than `num`.\n\n### Count and Sacrifice Calculation\n- If the count of numbers where `num ^ k` is greater than `num` is odd, find the minimum difference between any number in `nums` and its `num ^ k`. This minimum difference is called `sacrifice`.\n- The `sacrifice` is needed to adjust the final sum to be maximal when the count is odd. By subtracting this `sacrifice`, we ensure that the resulting sum is optimal.\n\n### Final Adjustment\n- If the count is odd, subtract the smallest `sacrifice` from the sum.\n- If the count is even, the initial sum is already optimal.\n\n## Complexity\n\n- **Time Complexity**: \\(O(n)\\)\n  - We iterate through the `nums` array once to compute the initial sum and count, which takes \\(O(n)\\).\n  - Finding the minimum `sacrifice` also takes \\(O(n)\\).\n  \n- **Space Complexity**: \\(O(1)\\)\n  - We use a constant amount of extra space regardless of the input size.\n\n## Solution\n\n```cpp\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n        long long sum = 0, cnt = 0;\n        int sacrifice = INT_MAX;\n        \n        for (int n : nums) {\n            int xorValue = n ^ k;\n            if (xorValue > n) {\n                sum += xorValue;\n                cnt++;\n                sacrifice = min(sacrifice, xorValue - n);\n            } else {\n                sum += n;\n                sacrifice = min(sacrifice, n - xorValue);\n            }\n        }\n        \n        if (cnt % 2 != 0) {\n            sum -= sacrifice;\n        }\n        \n        return sum;\n    }\n};\n
['Array', 'Greedy', 'C++']