initial
I didnt even get the q. But actually we are just interested whether flipping this pair of edges with XOR gives a bigger value for each node.
The core logic is
a^k is a different value from a. BUT
a^k^k = a.
So theres no point flipping it twice with xor.
So we are just interested if reatining original a value or flipping it once to get a^k will give us a bigger value.
Another core logic is that if we do even number of node flips, it is fine. That was the core pattern that i missed. It doesnt matter if we look at edges. If we have even number of nodes that we flipped, its a valid case. But if we flip odd number, it is invalid so to make it even we have to minus the extra odd flipped value.
reason why this is possible is cuz graph is bipartite- we can divide into red and blue nodes. Each pair has 1 red and 1 blue (or 0,1 node if u will).
solution
btw this c is
Even c → XOR 1 → becomes Odd
Odd c → XOR 1 → becomes Even
so at start is 0 and if we need to flip, we xor 1 so it becomes 1. and vice versa.
class Solution {
public long maximumValueSum(int[] nums, int k, int[][] edges) {
long ans = 0;
int count=0;
int minDiff = Integer.MAX_VALUE;
for(int num:nums){
int b = num^k;
ans+=Math.max(num,b);
if(b>num){
count ^= 1;
} else{
count ^=0;
}
minDiff = Math.min(minDiff, Math.abs(b-num));
}
return ans-minDiff*count;
}
}
complexity
n time 1 space
