XOR Paths
You are given the following:
A tree T consisting of n nodes
An integer x
Each node has some value w[i] associated with it.
Task
Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x.
Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once.
Example
Assumptions
n = 3
w = [3,2,2]
edges = [(1,2), (1,3)]
x = 1
Approach
There exist two simple paths such that bitwise xor of elements on the path is x
Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator.
Therefore, print 2.
A tree T consisting of n nodes
An integer x
Each node has some value w[i] associated with it.
Task
Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x.
Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once.
Example
Assumptions
n = 3
w = [3,2,2]
edges = [(1,2), (1,3)]
x = 1
Approach
There exist two simple paths such that bitwise xor of elements on the path is x
Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator.
Therefore, print 2.
Screw this idiot.
Not only does he double post but he just posts his homework with no attempt or question or anything.
On his 54th post.
Incredible.
Not only does he double post but he just posts his homework with no attempt or question or anything.
On his 54th post.
Incredible.
| Assumptions |
No assumptions need be made, we have ourselves a major waste of bandwidth and an oxygen thief.
@cool123dude,
Thanks!
max
| Rules & Regulations for posting on C++ forums 1: Try your best to solve your problem on your own before posting; no one appreciates people dumping their homework assignments without even trying to do them first. 2: Explain your problem or assignment very clearly (or just post the assignment itself). 3: Post whatever code you have already written, so we can see that you've actually made some effort on it, as well as any compiler errors, warnings, etc that you are having trouble with. This is linked to 1 above. 4: When you post your code, use code tags: http://www.cplusplus.com/articles/jEywvCM9/ http://www.cplusplus.com/articles/z13hAqkS/ It makes your code easier to read, along with proper indenting (just copy and paste your code directly from your IDE to preserve formatting). Rules&Regs, @JRmanx, from stackoverflow.com |
Thanks!
max
Topic archived. No new replies allowed.