Number of nodes with value one

Array Tree Depth-First Search Breadth-First Search Binary Tree

66.4% acceptance

Mar 31, 2026

There is an undirected connected tree with n nodes labeled from 1 to n and n - 1 edges. You are given the integer n. The parent node of a node with a label v is the node with the label floor (v / 2). The root of the tree is the node with the label 1. For example, if n = 7, then the node with the label 3 has the node with the label floor(3 / 2) = 1 as its parent, and the node with the label 7 has the node with the label floor(7 / 2) = 3 as its parent. You are also given an integer array queries. Initially, every node has a value 0 on it. For each query queries[i], you should flip all values in the subtree of the node with the label queries[i]. Return the total number of nodes with the value 1 after processing all the queries. Note that: Flipping the value of a node means that the node with the value 0 becomes 1 and vice versa. floor(x) is equivalent to rounding x down to the nearest integer.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_nodes(n: i32, queries: Vec<i32>) -> i32 {
    let n = n as usize;
    let mut cnt = vec![0u32; n + 1];
    for q in queries {
      cnt[q as usize] += 1;
    }
    // Propagate from root: total flips for node i = cnt[i] + flips from parent
    for i in 2..=n {
      cnt[i] += cnt[i / 2];
    }
    (1..=n).filter(|&i| cnt[i] % 2 == 1).count() as i32
  }
}