Maximum Genetic Difference Query - Practice Coding Problems

Maximum Genetic Difference Query - Problem

There is a rooted tree consisting of n nodes numbered 0 to n - 1. Each node's number denotes its unique genetic value (i.e., the genetic value of node x is x). The genetic difference between two genetic values is defined as the bitwise-XOR of their values.

You are given the integer array parents, where parents[i] is the parent for node i. If node x is the root of the tree, then parents[x] == -1.

You are also given the array queries where queries[i] = [nodei, vali]. For each query i, find the maximum genetic difference between vali and pi, where pi is the genetic value of any node that is on the path between nodei and the root (including nodei and the root). More formally, you want to maximize vali XOR pi.

Return an array ans where ans[i] is the answer to the ith query.

Input & Output

Example 1 — Basic Tree Queries

$ Input: parents = [-1,0,0,2], queries = [[3,4],[2,5]]

› Output: [7,5]

💡 Note: Tree: 0 is root, 1 and 2 are children of 0, 3 is child of 2. Query [3,4]: ancestors of 3 are [3,2,0], max XOR is 4⊕3=7. Query [2,5]: ancestors of 2 are [2,0], max XOR is 5⊕0=5.

Example 2 — Single Node Tree

$ Input: parents = [-1], queries = [[0,1]]

› Output: [1]

💡 Note: Only node 0 exists as root. Query [0,1]: only ancestor is node 0, so XOR is 1⊕0=1.

Example 3 — Linear Tree Path

$ Input: parents = [-1,0,1], queries = [[2,3]]

› Output: [3]

💡 Note: Linear tree: 0→1→2. Query [2,3]: ancestors are [2,1,0], XOR values are 3⊕2=1, 3⊕1=2, 3⊕0=3, so maximum is 3.

Constraints

n == parents.length
2 ≤ n ≤ 10⁵
0 ≤ parents[i] ≤ n - 1 for i ≠ root
parents[root] == -1
1 ≤ queries.length ≤ 3 × 10⁴
0 ≤ node_i ≤ n - 1
0 ≤ val_i ≤ 2 × 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Tree structure from parents array and queries with [node, value]

Process

For each query, find all ancestors and compute maximum XOR

Output

Array of maximum XOR values for each query

Key Takeaway

🎯 Key Insight: Use trie data structure to efficiently find maximum XOR by choosing opposite bits at each level

Asked in

G Google 25 a Amazon 18 M Microsoft 15 A Apple 12

The key insight is to use a trie data structure during DFS traversal to efficiently find maximum XOR values. The optimal approach uses DFS with trie to achieve O(N + Q × log(MAX_VAL)) time complexity. Time: O(N + Q × log V), Space: O(N × log V)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Path Finding	O(Q × N)	O(N)	For each query, find all ancestors and compute maximum XOR
DFS with Trie Optimization	O(N + Q × log(MAX_VAL))	O(N × log(MAX_VAL))	Use DFS traversal with trie to efficiently find maximum XOR

Brute Force with Path Finding — Algorithm Steps

Build tree structure from parents array
For each query, find path from node to root
Calculate XOR of query value with each ancestor
Return maximum XOR for each query

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create tree structure from parents array

Find Path

For each query, traverse from node to root

Calculate XOR

Compute maximum XOR with all ancestors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* parents, int parentsSize, int** queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int node = queries[i][0];
        int val = queries[i][1];
        
        // Get ancestors and find max XOR
        int maxXor = 0;
        int current = node;
        while (current != -1) {
            int xorVal = val ^ current;
            if (xorVal > maxXor) {
                maxXor = xorVal;
            }
            current = parents[current];
        }
        result[i] = maxXor;
    }
    
    return result;
}

int main() {
    // Simple implementation for testing
    int parents[] = {-1, 0, 0, 2};
    int* queries[2];
    int q1[] = {3, 4};
    int q2[] = {2, 5};
    queries[0] = q1;
    queries[1] = q2;
    
    int returnSize;
    int* result = solution(parents, 4, queries, 2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(Q × N)

Q queries × N nodes in worst case path length

✓ Linear Growth

Space Complexity

O(N)

Tree structure storage and recursion stack

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Path Finding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler