We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Sum of Node Values

Number: 3307

Difficulty: Hard

Paid? No

Companies: Google, Deutsche Bank

Problem Description

Given a tree with n nodes (0-indexed) where each node i has a value nums[i], you are allowed to perform an operation any number of times. In each operation, you choose an edge [u, v] and update:

  • nums[u] = nums[u] XOR k
  • nums[v] = nums[v] XOR k You want to maximize the sum of all node values. Return the maximum sum achievable.

Key Insights

  • The operation toggles the value at two endpoints simultaneously.
  • If we represent a toggle decision for each node as 0 (not toggled) or 1 (toggled), each operation flips two nodes so the overall parity (sum modulo 2) of toggles is even.
  • This means you can achieve any toggle configuration where an even number of nodes are toggled.
  • For each node, define diff = (nums[i] XOR k) - nums[i]. Toggling node i increases the sum by diff.
  • The problem reduces to selecting an even-sized subset of nodes to toggle such that the total addition (sum of diffs) is maximized.
  • A greedy approach is to add positive diffs, but if the count of beneficial toggles is odd, fix parity by either removing the one with the smallest positive diff or adding one extra node from the non-beneficial group (which might have diff ≤ 0).

Space and Time Complexity

Time Complexity: O(n) — scan through the nodes to compute diffs and determine the optimal even-parity toggling choice. Space Complexity: O(n) — used for storing diffs (or can be done in O(1) extra space with careful bookkeeping).

Solution

We start by computing the initial sum of nums. For each node i, define diff[i] = (nums[i] XOR k) - nums[i]. Toggling a node gives an increase of diff[i] to the total sum. It is optimal to toggle a node if diff[i] > 0. However, because the overall number of toggles must be even, we have two cases:

  1. If the number of nodes with diff > 0 is even, toggle all of them.
  2. If it is odd, fix parity by either:
    • Not toggling the node with the smallest positive diff (losing that benefit).
    • Toggling one additional node that originally wouldn’t be toggled (a node with diff ≤ 0), choosing the one with the maximum diff from that group. Our answer is the maximum of the sum with these adjustments and the original sum (if no toggles lead to an improvement).

The tree structure does not restrict the toggling choices because any even-number toggle assignment is achievable in a tree.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def maximumSum(self, nums, k, edges):
        # Calculate initial sum of the nodes
        initial_sum = sum(nums)
        
        # Calculate the difference value for each node if toggled
        diff_list = [(num ^ k) - num for num in nums]
        
        # Lists to store diffs that are positive (beneficial) and non-positive (non-beneficial)
        positive_diffs = [d for d in diff_list if d > 0]
        non_positive_diffs = [d for d in diff_list if d <= 0]
        
        # Base candidate: if we do not perform any toggles, sum remains initial_sum
        best_total = initial_sum
        
        # Sum of all beneficial diffs if toggled
        sum_positive = sum(positive_diffs)
        count_positive = len(positive_diffs)
        
        # Case 1: even number of beneficial toggles
        if count_positive % 2 == 0:
            candidate_sum = initial_sum + sum_positive
            best_total = max(best_total, candidate_sum)
        else:
            # Option 1: Do not toggle one beneficial node with minimum diff
            if positive_diffs:
                min_positive = min(positive_diffs)
                candidate_sum1 = initial_sum + sum_positive - min_positive
            else:
                candidate_sum1 = initial_sum  # fallback
            
            # Option 2: Also consider toggling one non-beneficial node (if exists)
            if non_positive_diffs:
                max_non_positive = max(non_positive_diffs)
                candidate_sum2 = initial_sum + sum_positive + max_non_positive
            else:
                candidate_sum2 = float('-inf')
            
            best_total = max(best_total, candidate_sum1, candidate_sum2)
        
        return best_total

# Example usage:
# sol = Solution()
# print(sol.maximumSum([1,2,1], 3, [[0,1],[0,2]]))  # Expected output: 6
← Back to All Questions