Tap here to switch tabs
Problem
Submissions

Problem: Number of Nodes With Value One

Try to solve the Number of Nodes With Value One problem.

Statement

There is a tree with n nodes numbered from 11 to n, rooted at node 11. For any node i where 2≤i≤2 \leq i \leq n, its parent is node ⌊i2⌋\lfloor \frac{i}{2} \rfloor. Initially, every node in the tree has a value of 00.

You are given the integer n and an integer array queries. For each value in queries, you flip the value of every node in the subtree rooted at that node, changing each 00 to 11 and each 11 to 00.

Return the total number of nodes that have a value of 11 after all queries have been processed.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • 1≤1 \leq queries[i] ≤\leq n

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Number of Nodes With Value One

Try to solve the Number of Nodes With Value One problem.

Statement

There is a tree with n nodes numbered from 11 to n, rooted at node 11. For any node i where 2≤i≤2 \leq i \leq n, its parent is node ⌊i2⌋\lfloor \frac{i}{2} \rfloor. Initially, every node in the tree has a value of 00.

You are given the integer n and an integer array queries. For each value in queries, you flip the value of every node in the subtree rooted at that node, changing each 00 to 11 and each 11 to 00.

Return the total number of nodes that have a value of 11 after all queries have been processed.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • 1≤1 \leq queries[i] ≤\leq n