Tap here to switch tabs
Problem
Submissions

Problem: Number of Nodes With Value One

Number of Nodes With Value One starts with all values at zero in a binary tree rooted at node one, where each parent is its node number halved and rounded down. Flip each queried subtree and return the final count of ones.

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

Number of Nodes With Value One starts with all values at zero in a binary tree rooted at node one, where each parent is its node number halved and rounded down. Flip each queried subtree and return the final count of ones.

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