Skip to content

2445. Number of Nodes With Value One 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int numberOfNodes(int n, vector<int>& queries) {
    // flipped[i] := true if we should flip all the values in the subtree rooted
    // at i
    vector<bool> flipped(n + 1);

    for (const int query : queries)
      flipped[query] = flipped[query] ^ true;

    return dfs(1, 0, n, flipped);
  }

 private:
  int dfs(int label, int value, int n, const vector<bool>& flipped) {
    if (label > n)
      return 0;
    value ^= flipped[label];
    return value +  //
           dfs(label * 2, value, n, flipped) +
           dfs(label * 2 + 1, value, n, flipped);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int numberOfNodes(int n, int[] queries) {
    // flipped[i] := true if we should flip all the values in the subtree rooted
    // at i
    boolean[] flipped = new boolean[n + 1];

    for (final int query : queries)
      flipped[query] = flipped[query] ^ true;

    return dfs(1, 0, n, flipped);
  }

  private int dfs(int label, int value, int n, boolean[] flipped) {
    if (label > n)
      return 0;
    value ^= flipped[label] ? 1 : 0;
    return value +                          //
        dfs(label * 2, value, n, flipped) + //
        dfs(label * 2 + 1, value, n, flipped);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def numberOfNodes(self, n: int, queries: list[int]) -> int:
    # flipped[i] := True if we should flip all the values in the subtree rooted
    # at i
    flipped = [False] * (n + 1)

    for query in queries:
      flipped[query] = flipped[query] ^ True

    def dfs(label: int, value: int) -> int:
      if label > n:
        return 0
      value ^= flipped[label]
      return value + dfs(label * 2, value) + dfs(label * 2 + 1, value)

    return dfs(1, 0)