We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Nodes With Value One

Number: 2584

Difficulty: Medium

Paid? Yes

Companies: Infosys

Problem Description

Given a tree with n nodes (labeled from 1 to n) where the parent of any node v is floor(v/2) (with node 1 as the root), initially every node has a value 0. For each query in the array queries, flip all values in the subtree of the node with that label (flipping means converting 0 to 1 and vice versa). Return the total number of nodes with value 1 after processing all the queries.

Key Insights

  • The tree has a natural structure similar to a binary heap where for any node v, its children (if they exist) are 2v and 2v+1.
  • A subtree flip can be thought of as toggling a flip flag over a range of nodes.
  • Using an Euler Tour / DFS traversal, we can record an entry (in) and exit (out) time for each node such that the subtree of any node forms a contiguous segment.
  • We can then perform range updates (increment at the entry time and decrement at the exit time) and later compute the prefix sum to determine if a node was flipped an odd number of times (resulting in a value 1) or an even number of times (remaining 0).

Space and Time Complexity

Time Complexity: O(n + q) where n is the number of nodes and q is the number of queries. Space Complexity: O(n) for storing the Euler Tour information and difference array.

Solution

We solve the problem by leveraging an Euler Tour technique:

  1. Perform a DFS from the root to record in and out times for each node; due to the binary tree structure, the children of node i are 2i and 2i+1 if they exist (i.e., if they are ≤ n).
  2. Create an auxiliary array (diff) representing a difference array over the Euler Tour ordering.
  3. For each query with node v, update diff[in[v]] by adding 1 and diff[out[v]] by subtracting 1. This marks the segment corresponding to the subtree of v to be flipped.
  4. Process the difference array to build a prefix sum array, and for each node check if the prefix sum is odd. If so, the node’s value is 1; otherwise, it remains 0.
  5. Count the number of nodes with value 1.

This approach avoids individually processing each subtree per query, making it efficient even with up to 10^5 nodes and queries.

Code Solutions

# Python solution using DFS and Euler Tour technique

import sys
sys.setrecursionlimit(200000)  # Increase recursion limit for deep recursion

def numberOfNodesWithValueOne(n, queries):
    # Build the arrays for Euler Tour
    in_time = [0] * (n + 1)   # in_time[i] is the time we enter node i
    out_time = [0] * (n + 1)  # out_time[i] is the time we exit node i
    euler_timer = 0

    # DFS function to perform Euler Tour
    def dfs(node):
        nonlocal euler_timer
        in_time[node] = euler_timer
        euler_timer += 1
        # The children of node are 2*node and 2*node+1 if within bounds
        left = 2 * node
        right = 2 * node + 1
        if left <= n:
            dfs(left)
        if right <= n:
            dfs(right)
        out_time[node] = euler_timer

    dfs(1)  # Start DFS from the root

    # Initialize the difference array for the Euler Tour positions
    diff = [0] * (n + 1)
    
    # Process each query: update the diff for the subtree range of the queried node.
    for node in queries:
        diff[in_time[node]] += 1
        diff[out_time[node]] -= 1

    # Build prefix sum over the Euler Tour order and check parity
    count = 0
    current_flip = 0
    # The Euler Tour covers n positions (since each node is visited once)
    for i in range(n):
        current_flip += diff[i]
        if current_flip % 2 == 1:
            count += 1

    return count

# Example usage:
print(numberOfNodesWithValueOne(5, [1, 2, 5]))  # Expected output: 3
← Back to All Questions