XOR to the Max

Tree Vibees - XORing to the Max

Problem Statement

You’re given a tree with n nodes numbered from 0 to n - 1, and a 0-indexed array nums where nums[i] is the value of the i-th node. You’re also given a positive integer k.

You can perform the following operation any number of times:

  • Pick an edge [u, v] and set:

    • nums[u] = nums[u] ^ k

    • nums[v] = nums[v] ^ k

Return the maximum possible sum of all nums[i] after performing any number of such operations.

Example:

Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
Output: 6
Explanation: Choose edge [0,2]: nums becomes [2,2,2] => sum = 6

Best Data Structure for Solving the Problem

This is a classic greedy XOR game on a tree. Since any edge can be used, and operations are reversible, the tree structure becomes less important here. So no need to traverse the tree!

  • We mainly need: Arrays and bitwise operations.

  • Optional but interview-valuable: Dynamic Programming on Trees (for variations).

Multiple Approaches

Approach 1: Greedy Bitwise XOR Strategy 

Idea:
Every node can be XORed with k. The decision is whether doing so increases the sum.
BUT: Since operations are done in pairs (edge involves 2 nodes), the total number of XOR operations must be even.

If the number of beneficial XORs is even: Do them all.
If odd: Do all but the least beneficial one.

class Solution {
  public long maximumValueSum(int[] nums, int k, int[][] edges) {
    long maxSum = 0;
    int changedCount = 0;
    int minChangeDiff = Integer.MAX_VALUE;

    for (int num : nums) {
      int xorVal = num ^ k;
      maxSum += Math.max(num, xorVal);
      if (xorVal > num) changedCount++;
      minChangeDiff = Math.min(minChangeDiff, Math.abs(num - xorVal));
    }

    return (changedCount % 2 == 0) ? maxSum : maxSum - minChangeDiff;
  }
}

Approach 2: DFS + Dynamic Programming on Tree (More Theoretical)

Idea:
If the problem was about paths or subtrees, we could use DP on trees. But here it's not necessary.
Still, it's good to mention this for completeness in interviews.


import java.util.*;

class Solution {

    List<List<Integer>> graph;

    int[] nums;

    int k;

    public long maximumValueSum(int[] nums, int k, int[][] edges) {

        this.nums = nums;

        this.k = k;

        int n = nums.length;

        graph = new ArrayList<>();

        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        for (int[] edge : edges) {

            graph.get(edge[0]).add(edge[1]);

            graph.get(edge[1]).add(edge[0]);

        }

        long[][] dp = new long[n][2];

        dfs(0, -1, dp);

        return Math.max(dp[0][0], dp[0][1]);

    }


    private void dfs(int node, int parent, long[][] dp) {

        dp[node][0] = nums[node];

        dp[node][1] = nums[node] ^ k;

        for (int child : graph.get(node)) {

            if (child == parent) continue;

            dfs(child, node, dp);

            dp[node][0] += Math.max(dp[child][0], dp[child][1]);

            dp[node][1] += Math.max(dp[child][0], dp[child][1]);

        }

    }

    public static void main(String[] args) {

        Solution sol = new Solution();

        int[] nums = {1, 2, 1};

        int k = 3;

        int[][] edges = {{0,1}, {0,2}};

        System.out.println(sol.maximumValueSum(nums, k, edges));

    }

}

⚠️ Common Mistakes and Pitfalls

  • Assuming you have to traverse the tree — you don’t!

  • Forgetting the operation is on pairs → total XOR ops must be even

  • Ignoring the case where skipping one less beneficial XOR increases the overall sum

  • Misunderstanding bitwise XOR behavior: a ^ k can be smaller or larger than a

📊 Time and Space Complexity Analysis

Step         Time Complexity        Space Complexity
Greedy XOR approach            O(n)            O(1)
Tree building (unused)            O(n)            O(n)

Where n = number of nodes

🌍 Real-World Applications

  • Encryption toggles (XOR is commonly used)

  • Bitmasking problems in scheduling, resource allocation

  • XOR-swap logic in systems with limited memory

  • Graph operations optimization


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Minimum equal sum

Minimum Equal Sum – Matching Arrays with Smart Replacements Problem Statement You are given two integer arrays nums1 and nums2 , which may contain zeros. You must replace each 0 with a strictly positive integer (≥ 1) such that the sum of both arrays becomes equal . Your goal is to minimize that common equal sum after all replacements. If there is no way to make the sums equal with any valid replacements, return -1 . Example Input: nums1 = [ 3 , 2 , 0 , 1 , 0 ] nums2 = [ 6 , 5 , 0 ] Output: 12 Explanation: Replace the two zeros in nums1 with 2 and 4 → [3,2,2,1,4] Replace the zero in nums2 with 1 → [6,5,1] Both arrays now sum to 12 . Best Data Structure for the Job This problem is mostly numerical, so there’s no need for complex data structures like trees or heaps. What you do need is: A way to count zeros and compute current sums. Simple math to determine possible ranges. Long data type to handle large sums. Different Approaches Approach 1: Brute Fo...
Read more