AND path in a binary tree

4.2

19 votes
Datastructures, Query, Dynamic Programming, Algorithms, Memoization
Problem

You are given Q queries and for each query, there is a Binary Tree with N vertices numbered 1 through N. For each i from 2 to N, there is an edge between vertex i and vertex i/2 (rounded down). Count number of paths such that bitwise AND of all nodes on that path is odd. A path will be considered valid if the number of nodes on that path is greater than 1.
Note: The value of the nodes is equal to the indices.

Input:
The first line of the input contains a single integer Q denoting the number of queries. The description of Q queries follows: A single line having the value of N.

Output:
For each query, print a single line containing one integer — the number of paths such that bitwise AND of all nodes on that path is odd.

Constraints:

1Q,N105

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Query 1: The is only one valid path 1-3.
Query 2: The valid paths are, [1-3, 1-3-7, 3-7].
Query 3: The valid paths are, [1-3, 1-3-7, 3-7, 5-11].

 

Editor Image

?