# Count of paths in given Binary Tree with odd bitwise AND for Q queries

Given an **integer Q** representing the number of queries and an array where each query has an integer **N**. Our task is to iterate through each query and find the number of paths such that bitwise AND of all nodes on that path is odd.

A binary tree is constructed 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 off).

**Examples:**

Input:Q = 2, [5, 2]Output:1 0Explanation:For first query the binary tree will be 1 / \ 2 3 / \ 4 5 The path which satisfies the condition is 1 -> 3. Hence only 1 path. For the second query, the binary tree will be 1 / 2 There no such path that satisfies the condition.Input:Q = 3, [3, 7, 13]Output:1 3 4

**Approach:** The idea is to use Dynamic Programming and **precomputation** of answers for all values from 1 to the maximum value of N in the query.

- Firstly, observe that if a bitwise AND of a path is odd, then
**none elements of that path can be even**. Hence, the required path should have odd elements. - We know that for an i
^{th}node (except for node 1) the parent node will be i/2 (rounded off). Maintain a**dp array**for storing the answer for the i^{th}node. Another array will be used to store the number of odd elements from the current node until the parents are odd. - While computing the dp array, the first condition is if the i
^{th}node value is even, then**dp[i] = dp[i – 1]**because the i^{th}node will not contribute to the answer, so dp[i] will be the answer to (i-1)^{th}node. Secondly, if i^{th}node is odd, then dp[i] = dp[i-1] + nC2 -(n-1)C2. On simplification**dp[i] = dp[i-1] + (number of odd elements till now) – 1.**

Below is the implementation of the above approach:

## C++

`// C++ implementation to count` `// paths in Binary Tree` `// with odd bitwise AND` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count number of paths` `// in binary tree such that bitwise` `// AND of all nodes is Odd` `void` `compute(vector<` `int` `> query)` `{` ` ` `// vector v for storing` ` ` `// the count of odd numbers` ` ` `// vector dp to store the` ` ` `// count of bitwise odd paths` ` ` `// till that vertex` ` ` `vector<` `int` `> v(100001), dp(100001);` ` ` `v[1] = 1, v[2] = 0;` ` ` `dp[1] = 0, dp[2] = 0;` ` ` `// Precomputing for each value` ` ` `for` `(` `int` `i = 3; i < 100001; i++) {` ` ` `// check for odd value` ` ` `if` `(i % 2 != 0) {` ` ` `if` `((i / 2) % 2 == 0) {` ` ` `v[i] = 1;` ` ` `dp[i] = dp[i - 1];` ` ` `}` ` ` `else` `{` ` ` `// Number of odd elements will` ` ` `// be +1 till the parent node` ` ` `v[i] = v[i / 2] + 1;` ` ` `dp[i] = dp[i - 1] + v[i] - 1;` ` ` `}` ` ` `}` ` ` `// For even case` ` ` `else` `{` ` ` `// Since node is even` ` ` `// Number of odd elements` ` ` `// will be 0` ` ` `v[i] = 0;` ` ` `// Even value node will` ` ` `// not contribute in answer` ` ` `// hence dp[i] = previous answer` ` ` `dp[i] = dp[i - 1];` ` ` `}` ` ` `}` ` ` `// Printing the answer` ` ` `// for each query` ` ` `for` `(` `auto` `x : query)` ` ` `cout << dp[x] << endl;` `}` `// Driver code` `int` `main()` `{` ` ` `// vector to store queries` ` ` `vector<` `int` `> query = { 5, 2 };` ` ` `compute(query);` ` ` `return` `0;` `}` |

## Java

`// Java implementation to count` `// paths in Binary Tree` `// with odd bitwise AND` `class` `GFG{` `// Function to count number of paths` `// in binary tree such that bitwise` `// AND of all nodes is Odd` `static` `void` `compute(` `int` `[] query)` `{` ` ` ` ` `// v for storing the count` ` ` `// of odd numbers` ` ` `// dp to store the count of` ` ` `// bitwise odd paths` ` ` `// till that vertex` ` ` `int` `[]v = ` `new` `int` `[` `100001` `];` ` ` `int` `[]dp = ` `new` `int` `[` `100001` `];` ` ` ` ` `v[` `1` `] = ` `1` `; v[` `2` `] = ` `0` `;` ` ` `dp[` `1` `] = ` `0` `; dp[` `2` `] = ` `0` `;` ` ` `// Precomputing for each value` ` ` `for` `(` `int` `i = ` `3` `; i < ` `100001` `; i++)` ` ` `{` ` ` ` ` `// Check for odd value` ` ` `if` `(i % ` `2` `!= ` `0` `)` ` ` `{` ` ` `if` `((i / ` `2` `) % ` `2` `== ` `0` `)` ` ` `{` ` ` `v[i] = ` `1` `;` ` ` `dp[i] = dp[i - ` `1` `];` ` ` `}` ` ` `else` ` ` `{` ` ` ` ` `// Number of odd elements will` ` ` `// be +1 till the parent node` ` ` `v[i] = v[i / ` `2` `] + ` `1` `;` ` ` `dp[i] = dp[i - ` `1` `] + v[i] - ` `1` `;` ` ` `}` ` ` `}` ` ` ` ` `// For even case` ` ` `else` ` ` `{` ` ` ` ` `// Since node is even` ` ` `// Number of odd elements` ` ` `// will be 0` ` ` `v[i] = ` `0` `;` ` ` ` ` `// Even value node will` ` ` `// not contribute in answer` ` ` `// hence dp[i] = previous answer` ` ` `dp[i] = dp[i - ` `1` `];` ` ` `}` ` ` `}` ` ` ` ` `// Printing the answer` ` ` `// for each query` ` ` `for` `(` `int` `x : query)` ` ` `System.out.print(dp[x] + ` `"\n"` `);` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` ` ` `// To store queries` ` ` `int` `[]query = { ` `5` `, ` `2` `};` ` ` ` ` `compute(query);` `}` `}` `// This code is contributed by Princi Singh` |

## Python3

`# Python3 implementation to count` `# paths in Binary Tree with odd` `# bitwise AND` `# Function to count number of paths` `# in binary tree such that bitwise` `# AND of all nodes is Odd` `def` `compute(query):` ` ` ` ` `# vector v for storing` ` ` `# the count of odd numbers` ` ` `# vector dp to store the` ` ` `# count of bitwise odd paths` ` ` `# till that vertex` ` ` `v ` `=` `[` `None` `] ` `*` `100001` ` ` `dp ` `=` `[` `None` `] ` `*` `100001` ` ` `v[` `1` `] ` `=` `1` ` ` `v[` `2` `] ` `=` `0` ` ` `dp[` `1` `] ` `=` `0` ` ` `dp[` `2` `] ` `=` `0` ` ` `# Precomputing for each value` ` ` `for` `i ` `in` `range` `(` `3` `, ` `100001` `):` ` ` ` ` `# Check for odd value` ` ` `if` `(i ` `%` `2` `!` `=` `0` `):` ` ` `if` `((i ` `/` `/` `2` `) ` `%` `2` `=` `=` `0` `):` ` ` `v[i] ` `=` `1` ` ` `dp[i] ` `=` `dp[i ` `-` `1` `]` ` ` `else` `:` ` ` ` ` `# Number of odd elements will` ` ` `# be +1 till the parent node` ` ` `v[i] ` `=` `v[i ` `/` `/` `2` `] ` `+` `1` ` ` `dp[i] ` `=` `dp[i ` `-` `1` `] ` `+` `v[i] ` `-` `1` ` ` `# For even case` ` ` `else` `:` ` ` ` ` `# Since node is even` ` ` `# Number of odd elements` ` ` `# will be 0` ` ` `v[i] ` `=` `0` ` ` `# Even value node will` ` ` `# not contribute in answer` ` ` `# hence dp[i] = previous answer` ` ` `dp[i] ` `=` `dp[i ` `-` `1` `]` ` ` `# Printing the answer` ` ` `# for each query` ` ` `for` `x ` `in` `query:` ` ` `print` `(dp[x])` `# Driver code` `# Vector to store queries` `query ` `=` `[ ` `5` `, ` `2` `]` `compute(query)` `# This code is contributed by sanjoy_62` |

## C#

`// C# implementation to count` `// paths in Binary Tree` `// with odd bitwise AND` `using` `System;` `class` `GFG{` `// Function to count number of paths` `// in binary tree such that bitwise` `// AND of all nodes is Odd` `static` `void` `compute(` `int` `[] query)` `{` ` ` ` ` `// v for storing the count` ` ` `// of odd numbers` ` ` `// dp to store the count of` ` ` `// bitwise odd paths` ` ` `// till that vertex` ` ` `int` `[]v = ` `new` `int` `[100001];` ` ` `int` `[]dp = ` `new` `int` `[100001];` ` ` ` ` `v[1] = 1; v[2] = 0;` ` ` `dp[1] = 0; dp[2] = 0;` ` ` `// Precomputing for each value` ` ` `for` `(` `int` `i = 3; i < 100001; i++)` ` ` `{` ` ` ` ` `// Check for odd value` ` ` `if` `(i % 2 != 0)` ` ` `{` ` ` `if` `((i / 2) % 2 == 0)` ` ` `{` ` ` `v[i] = 1;` ` ` `dp[i] = dp[i - 1];` ` ` `}` ` ` `else` ` ` `{` ` ` ` ` `// Number of odd elements will` ` ` `// be +1 till the parent node` ` ` `v[i] = v[i / 2] + 1;` ` ` `dp[i] = dp[i - 1] + v[i] - 1;` ` ` `}` ` ` `}` ` ` ` ` `// For even case` ` ` `else` ` ` `{` ` ` ` ` `// Since node is even` ` ` `// Number of odd elements` ` ` `// will be 0` ` ` `v[i] = 0;` ` ` ` ` `// Even value node will` ` ` `// not contribute in answer` ` ` `// hence dp[i] = previous answer` ` ` `dp[i] = dp[i - 1];` ` ` `}` ` ` `}` ` ` ` ` `// Printing the answer` ` ` `// for each query` ` ` `foreach` `(` `int` `x ` `in` `query)` ` ` `Console.Write(dp[x] + ` `"\n"` `);` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` ` ` `// To store queries` ` ` `int` `[]query = { 5, 2 };` ` ` ` ` `compute(query);` `}` `}` `// This code is contributed by Amit Katiyar` |

## Javascript

`<script>` `// Javascript implementation to count` `// paths in Binary Tree` `// with odd bitwise AND` `// Function to count number of paths` `// in binary tree such that bitwise` `// AND of all nodes is Odd` `function` `compute(query)` `{` ` ` `// vector v for storing` ` ` `// the count of odd numbers` ` ` `// vector dp to store the` ` ` `// count of bitwise odd paths` ` ` `// till that vertex` ` ` `var` `v = Array(100001).fill(0);` ` ` `var` `dp = Array(100001).fill(0);` ` ` `v[1] = 1, v[2] = 0;` ` ` `dp[1] = 0, dp[2] = 0;` ` ` `// Precomputing for each value` ` ` `for` `(` `var` `i = 3; i < 100001; i++) {` ` ` `// check for odd value` ` ` `if` `(i % 2 != 0) {` ` ` `if` `(parseInt(i / 2) % 2 == 0) {` ` ` `v[i] = 1;` ` ` `dp[i] = dp[i - 1];` ` ` `}` ` ` `else` `{` ` ` `// Number of odd elements will` ` ` `// be +1 till the parent node` ` ` `v[i] = v[parseInt(i / 2)] + 1;` ` ` `dp[i] = dp[i - 1] + v[i] - 1;` ` ` `}` ` ` `}` ` ` `// For even case` ` ` `else` `{` ` ` `// Since node is even` ` ` `// Number of odd elements` ` ` `// will be 0` ` ` `v[i] = 0;` ` ` `// Even value node will` ` ` `// not contribute in answer` ` ` `// hence dp[i] = previous answer` ` ` `dp[i] = dp[i - 1];` ` ` `}` ` ` `}` ` ` `// Printing the answer` ` ` `// for each query` ` ` `query.forEach(x => {` ` ` ` ` `document.write( dp[x] + ` `"<br>"` `);` ` ` `});` `}` `// Driver code` `// vector to store queries` `var` `query = [5, 2];` `compute(query);` `</script>` |

**Output:**

1 0

* Time Complexity: O( Nmax + Q*(1) )*, where Nmax is the maximum value of N. Q*(1) since we are precomputing each query.

**Auxiliary Space**: O(Nmax)