12 days ago

Rohit • 40

Hyderabad

Question: Lucky Path

Problem Statement:

You are given a tree with N nodes rooted at node 1. Each node has an integer value value[i].

A lucky path is defined as a path from the root to any leaf such that the sum of all node values on that path is divisible by K.

Find the total number of lucky paths in the tree.

Notes:

• A tree is a connected acyclic graph with N nodes and N - 1 edges.

Input Format:

• The first line contains an integer, N, denoting the number of nodes.
• The next line contains an integer, K.
• Each line i of the N subsequent lines (where 0 <= i < N) contains 2 space-separated integers each describing the row Edges[i], the edge (0,0) must be ignored.
• (Further input lines will contain the node values).

13 hours ago

admin 1.9k

Sehore

Problem1 Solution

Lucky Path Solution

Topics Involved / Prerequisites

• Graph Theory / Trees
• Depth-First Search (DFS)
• Modular Arithmetic

Overview

The problem requires us to find paths from the root (node 1) to any leaf node where the total sum of the node values modulo K equals 0.

Because the structure is a tree, there is exactly one unique path from the root to any given leaf. We can use a Depth-First Search (DFS) to traverse down the tree, carrying the running sum of the path modulo K. When we hit a leaf, we check if our running sum perfectly divides by K.

Approach

1. Tree Construction

We build an adjacency list to represent the undirected tree. The problem mentions a quirk where an edge of(0, 0)might be provided and must be ignored. We loop through the given edges, filter out the(0, 0)edge, and construct bidirectional links for the rest.

2. Depth-First Search (DFS)

We initiate a DFS starting from node 1. We pass three primary variables down the recursive calls: thecurrent_node, itsparent(to prevent traversing backward), and thecurrent_sumof the path.

At each node, we update the sum:current_sum = (current_sum + value[current_node]) % K. To safely handle potential negative integer values, we apply a robust modulo operation:((current_sum % K) + K) % K.

3. Leaf Identification & Counting

During the DFS, a node is identified as a leaf if it has no neighbors other than itsparent. If we determine the current node is a leaf, we check if thecurrent_sumis exactly 0. If it is, we've found a valid "lucky path" and increment our global counter.

Code Implementation

#include <iostream>
#include <vector>

using namespace std;

class LuckyTree {
    int lucky_count = 0;
    
    void dfs(int node, int parent, long long current_sum, int K, 
             const vector<vector<int>>& adj, const vector<int>& values) {
        
        // Add current node's value and safely apply modulo K
        current_sum = ((current_sum + values[node]) % K + K) % K;
        
        bool is_leaf = true;
        
        // Traverse all connected neighbors
        for (int neighbor : adj[node]) {
            if (neighbor != parent) {
                is_leaf = false; // If it has a child, it's not a leaf
                dfs(neighbor, node, current_sum, K, adj, values);
            }
        }
        
        // If it's a leaf and the path sum is divisible by K
        if (is_leaf && current_sum == 0) {
            lucky_count++;
        }
    }

public:
    int countLuckyPaths(int N, int K, const vector<pair<int, int>>& edges, const vector<int>& values) {
        // 1-based indexing for the adjacency list
        vector<vector<int>> adj(N + 1);
        
        for (const auto& edge : edges) {
            int u = edge.first;
            int v = edge.second;
            // Ignore the (0, 0) edge as per problem statement
            if (u == 0 && v == 0) continue;
            
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        lucky_count = 0;
        // Start DFS from root node 1, parent is -1, initial sum is 0
        dfs(1, -1, 0, K, adj, values);
        
        return lucky_count;
    }
};

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    // Read edges (N lines as specified by the prompt quirk)
    vector<pair<int, int>> edges;
    for (int i = 0; i < N; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
    }

    // Read node values (assuming 1-based indexing for N nodes)
    vector<int> values(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> values[i];
    }

    LuckyTree treeSolver;
    cout << treeSolver.countLuckyPaths(N, K, edges, values) << "\n";

    return 0;
}

Time and Space Complexity

• Time Complexity:O(N) — We visit each node and traverse each edge exactly once during the DFS.
• Space Complexity:O(N) — The adjacency list requires O(N) space, and the maximum depth of the recursive DFS call stack could be O(N) in the case of a skewed (line-like) tree.