Maximum XOR of Two Numbers

🎯

Maximum XOR of Two Numbers

mediumBIT_MANIPULATIONAmazonGoogleFacebook

Imagine you have a list of secret codes represented as numbers, and you want to find the pair of codes that differ the most in their binary form to maximize security.

💡 This problem is about understanding how XOR works at the bit level and how to cleverly find two numbers that produce the largest XOR value. Beginners often struggle because the brute force approach is straightforward but inefficient, and the optimal solution requires a bitwise greedy strategy that is less intuitive.

📋

Problem Statement

Given an array of integers nums, find the maximum result of nums[i] XOR nums[j] where 0 ≤ i, j < n and i != j. Return the maximum XOR value.

1 ≤ n ≤ 10^50 ≤ nums[i] < 2^31

💡

Example

Input"[3, 10, 5, 25, 2, 8]"

Output28

The maximum XOR is 5 ^ 25 = 28.

• Array with all zeros → maximum XOR is 0
• Array with one element → maximum XOR is 0 (no pair)
• Array with two identical elements → maximum XOR is 0
• Array with maximum integer values → test handling of large bits

⚠️

Common Mistakes

Using brute force for large inputs

Code runs too slowly or times out

✅ Implement the greedy bit-by-bit or trie approach

Not masking prefixes correctly in greedy approach

Incorrect prefixes lead to wrong maximum XOR

✅ Ensure mask includes all bits from current bit to most significant bit

In trie approach, not checking for null children before traversal

Runtime errors or crashes

✅ Always check if child node exists before moving down the trie

Confusing XOR with OR or AND in logic

Wrong results, failing test cases

✅ Remember XOR properties and use ^ operator correctly

Not handling edge cases like single element arrays

Incorrect output or errors

✅ Return 0 when no pairs exist or handle gracefully

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by trying all pairs. It is simple but inefficient, helping beginners understand the problem's nature before optimizing.

Intuition

Try every possible pair of numbers and compute their XOR, keeping track of the maximum XOR found.

Algorithm

1. Initialize max_xor to 0.
2. Use two nested loops to iterate over all pairs (i, j) with i < j.
3. Calculate XOR of nums[i] and nums[j].
4. Update max_xor if the current XOR is greater.

💡 The nested loops make it easy to understand but hide the inefficiency until you analyze the time complexity.

</>

Code

def findMaximumXOR(nums):
    max_xor = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            current_xor = nums[i] ^ nums[j]
            if current_xor > max_xor:
                max_xor = current_xor
    return max_xor

# Driver code
if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

Line Notes

max_xor = 0Initialize the variable to keep track of the maximum XOR found so far.

for i in range(n)Outer loop selects the first number in the pair.

for j in range(i + 1, n)Inner loop selects the second number, avoiding duplicate pairs and self-pairing.

current_xor = nums[i] ^ nums[j]Calculate XOR of the current pair to check if it's the maximum.

public class Solution {
    public static int findMaximumXOR(int[] nums) {
        int maxXor = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentXor = nums[i] ^ nums[j];
                if (currentXor > maxXor) {
                    maxXor = currentXor;
                }
            }
        }
        return maxXor;
    }

    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(findMaximumXOR(nums)); // Output: 28
    }
}

Line Notes

int maxXor = 0;Initialize maxXor to store the maximum XOR found.

for (int i = 0; i < n; i++)Outer loop picks the first element of the pair.

for (int j = i + 1; j < n; j++)Inner loop picks the second element, ensuring no repeats or self-pairs.

int currentXor = nums[i] ^ nums[j];Compute XOR of the current pair to compare with maxXor.

#include <iostream>
#include <vector>
using namespace std;

int findMaximumXOR(vector<int>& nums) {
    int maxXor = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int currentXor = nums[i] ^ nums[j];
            if (currentXor > maxXor) {
                maxXor = currentXor;
            }
        }
    }
    return maxXor;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    cout << findMaximumXOR(nums) << endl; // Output: 28
    return 0;
}

Line Notes

int maxXor = 0;Initialize maxXor to track the highest XOR found.

for (int i = 0; i < n; i++)Outer loop selects the first number in the pair.

for (int j = i + 1; j < n; j++)Inner loop selects the second number, avoiding duplicates.

int currentXor = nums[i] ^ nums[j];Calculate XOR for the current pair to update maxXor if needed.

function findMaximumXOR(nums) {
    let maxXor = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const currentXor = nums[i] ^ nums[j];
            if (currentXor > maxXor) {
                maxXor = currentXor;
            }
        }
    }
    return maxXor;
}

// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // Output: 28

Line Notes

let maxXor = 0;Initialize maxXor to store the maximum XOR found so far.

for (let i = 0; i < n; i++)Outer loop picks the first element in the pair.

for (let j = i + 1; j < n; j++)Inner loop picks the second element, avoiding repeats and self-pairs.

const currentXor = nums[i] ^ nums[j];Calculate XOR of the current pair to check if it beats maxXor.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

We check every pair of n elements, resulting in n*(n-1)/2 operations, which is O(n^2). No extra space is used except variables.

💡 For n=20, this means about 190 operations, which is manageable, but for n=100000, it becomes 5 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, so it is useful only to understand the problem and as a baseline before optimizing.

🧠

Greedy Bit-by-Bit with Prefix Set

💡 This approach introduces a clever greedy strategy that builds the maximum XOR bit by bit from the most significant bit to the least, using a set of prefixes to check feasibility.

Intuition

Try to set the current bit in the answer to 1 if possible by checking if there exist two prefixes that can produce that bit set in XOR.

Algorithm

1. Initialize max_xor to 0.
2. Iterate from the highest bit (31) down to 0.
3. For each bit, build a set of prefixes of all numbers truncated to that bit.
4. Check if setting this bit in max_xor is possible by verifying if any two prefixes can produce that bit set in XOR.
5. If possible, update max_xor by setting this bit.

💡 This approach is tricky because it uses a greedy guess and set membership to confirm if the guess is valid, which is less intuitive than brute force.

</>

Code

def findMaximumXOR(nums):
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)
        prefixes = set([num & mask for num in nums])
        candidate = max_xor | (1 << i)
        for prefix in prefixes:
            if (candidate ^ prefix) in prefixes:
                max_xor = candidate
                break
    return max_xor

# Driver code
if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

Line Notes

max_xor = 0Initialize max_xor to store the maximum XOR found so far.

for i in range(31, -1, -1)Iterate over bits from the most significant (31) to least (0).

mask |= (1 << i)Update mask to include the current bit and all bits above it.

prefixes = set([num & mask for num in nums])Collect prefixes of all numbers truncated to current mask to check possible XOR pairs.

for prefix in prefixes:Check if there exists a pair of prefixes that can achieve the candidate XOR by leveraging XOR properties.

import java.util.*;

public class Solution {
    public static int findMaximumXOR(int[] nums) {
        int maxXor = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask = mask | (1 << i);
            Set<Integer> prefixes = new HashSet<>();
            for (int num : nums) {
                prefixes.add(num & mask);
            }
            int candidate = maxXor | (1 << i);
            for (int prefix : prefixes) {
                if (prefixes.contains(candidate ^ prefix)) {
                    maxXor = candidate;
                    break;
                }
            }
        }
        return maxXor;
    }

    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(findMaximumXOR(nums)); // Output: 28
    }
}

Line Notes

int maxXor = 0, mask = 0;Initialize maxXor and mask to track maximum XOR and current bit mask.

for (int i = 31; i >= 0; i--)Iterate bits from highest to lowest to build maxXor bit by bit.

mask = mask | (1 << i);Update mask to include current bit and all higher bits.

Set<Integer> prefixes = new HashSet<>();Store prefixes truncated to current mask to check XOR feasibility.

for (int prefix : prefixes)Check if any two prefixes can produce the candidate XOR by XORing with each other.

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int findMaximumXOR(vector<int>& nums) {
    int maxXor = 0, mask = 0;
    for (int i = 31; i >= 0; i--) {
        mask |= (1 << i);
        unordered_set<int> prefixes;
        for (int num : nums) {
            prefixes.insert(num & mask);
        }
        int candidate = maxXor | (1 << i);
        for (int prefix : prefixes) {
            if (prefixes.count(candidate ^ prefix)) {
                maxXor = candidate;
                break;
            }
        }
    }
    return maxXor;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    cout << findMaximumXOR(nums) << endl; // Output: 28
    return 0;
}

Line Notes

int maxXor = 0, mask = 0;Initialize maxXor and mask to track the maximum XOR and current bit mask.

for (int i = 31; i >= 0; i--)Iterate bits from most significant to least significant.

mask |= (1 << i);Update mask to include the current bit and all bits above it.

unordered_set<int> prefixes;Store prefixes truncated to the current mask to check if candidate XOR is possible.

for (int prefix : prefixes)Check if any two prefixes can produce the candidate XOR by XORing with each other.

function findMaximumXOR(nums) {
    let maxXor = 0, mask = 0;
    for (let i = 31; i >= 0; i--) {
        mask = mask | (1 << i);
        const prefixes = new Set();
        for (const num of nums) {
            prefixes.add(num & mask);
        }
        const candidate = maxXor | (1 << i);
        for (const prefix of prefixes) {
            if (prefixes.has(candidate ^ prefix)) {
                maxXor = candidate;
                break;
            }
        }
    }
    return maxXor;
}

// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // Output: 28

Line Notes

let maxXor = 0, mask = 0;Initialize maxXor and mask to track the maximum XOR and current bit mask.

for (let i = 31; i >= 0; i--)Iterate bits from highest to lowest to build maxXor bit by bit.

mask = mask | (1 << i);Update mask to include the current bit and all bits above it.

const prefixes = new Set();Store prefixes truncated to current mask to check if candidate XOR is possible.

for (const prefix of prefixes)Check if any two prefixes can produce the candidate XOR by XORing with each other.

⏱

Complexity

TimeO(n * log M)

SpaceO(n)

We iterate over 32 bits (log M where M is max number), and for each bit, we build a set of prefixes of size n, resulting in O(n * log M) time. Space is O(n) for the prefix set.

💡 For n=100000 and 32 bits, this means about 3.2 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews to demonstrate bit manipulation mastery.

🧠

Trie-Based Bitwise Solution

💡 This approach uses a binary trie (prefix tree) to store numbers bit by bit, allowing efficient queries to find the best XOR partner for each number.

Intuition

Insert all numbers into a trie representing bits from most significant to least. For each number, traverse the trie to greedily pick opposite bits to maximize XOR.

Algorithm

1. Build a trie with all numbers inserted bit by bit from the 31st to 0th bit.
2. For each number, traverse the trie to find the number that maximizes XOR by choosing opposite bits when possible.
3. Keep track of the maximum XOR found during these traversals.
4. Return the maximum XOR after processing all numbers.

💡 This approach is more complex due to the trie data structure but offers clear logic for maximizing XOR bitwise.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def findMaxXor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children.get(bit)
        return max_xor

def findMaximumXOR(nums):
    trie = Trie()
    for num in nums:
        trie.insert(num)
    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.findMaxXor(num))
    return max_xor

# Driver code
if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

Line Notes

class TrieNode:Define a node in the trie with children for bits 0 and 1.

def insert(self, num):Insert a number into the trie bit by bit from MSB to LSB.

def findMaxXor(self, num):Find the maximum XOR for num by traversing trie choosing opposite bits when possible.

max_xor = max(max_xor, trie.findMaxXor(num))Update global maximum XOR after checking each number.

for i in range(31, -1, -1):Traverse bits from most significant to least significant to find best XOR path.

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

public class Solution {
    TrieNode root = new TrieNode();

    public void insert(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }

    public int findMaxXor(int num) {
        TrieNode node = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node.children[toggledBit] != null) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }

    public int findMaximumXOR(int[] nums) {
        for (int num : nums) insert(num);
        int maxXor = 0;
        for (int num : nums) {
            maxXor = Math.max(maxXor, findMaxXor(num));
        }
        return maxXor;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(sol.findMaximumXOR(nums)); // Output: 28
    }
}

Line Notes

TrieNode[] children = new TrieNode[2];Each node has two children representing bits 0 and 1.

for (int i = 31; i >= 0; i--)Traverse bits from most significant to least significant to find best XOR path.

if (node.children[toggledBit] != null)Try to go opposite bit to maximize XOR at this bit position.

maxXor = Math.max(maxXor, findMaxXor(num));Update maximum XOR after querying trie for each number.

#include <iostream>
#include <vector>
using namespace std;

struct TrieNode {
    TrieNode* children[2] = {nullptr, nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
    }

    int findMaxXor(int num) {
        TrieNode* node = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node->children[toggledBit]) {
                maxXor |= (1 << i);
                node = node->children[toggledBit];
            } else {
                node = node->children[bit];
            }
        }
        return maxXor;
    }
};

int findMaximumXOR(vector<int>& nums) {
    Trie trie;
    for (int num : nums) trie.insert(num);
    int maxXor = 0;
    for (int num : nums) {
        maxXor = max(maxXor, trie.findMaxXor(num));
    }
    return maxXor;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    cout << findMaximumXOR(nums) << endl; // Output: 28
    return 0;
}

Line Notes

TrieNode* children[2] = {nullptr, nullptr};Each trie node has two children for bits 0 and 1.

for (int i = 31; i >= 0; i--)Traverse bits from most significant to least significant to find best XOR path.

if (node->children[toggledBit])Try to go opposite bit to maximize XOR at this bit position.

maxXor = max(maxXor, trie.findMaxXor(num));Update maximum XOR after querying trie for each number.

class TrieNode {
    constructor() {
        this.children = {};
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!(bit in node.children)) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }

    findMaxXor(num) {
        let node = this.root;
        let maxXor = 0;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const toggledBit = 1 - bit;
            if (toggledBit in node.children) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }
}

function findMaximumXOR(nums) {
    const trie = new Trie();
    for (const num of nums) trie.insert(num);
    let maxXor = 0;
    for (const num of nums) {
        maxXor = Math.max(maxXor, trie.findMaxXor(num));
    }
    return maxXor;
}

// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // Output: 28

Line Notes

this.children = {};Each trie node stores children for bits 0 and 1 as keys.

for (let i = 31; i >= 0; i--)Traverse bits from most significant to least significant to find best XOR path.

if (toggledBit in node.children)Try to go opposite bit to maximize XOR at this bit position.

maxXor = Math.max(maxXor, trie.findMaxXor(num));Update maximum XOR after querying trie for each number.

⏱

Complexity

TimeO(n * log M)

SpaceO(n * log M)

Inserting n numbers into a trie with log M bits each takes O(n log M). Querying each number also takes O(log M). Space is O(n log M) for the trie nodes.

💡 For n=100000 and 32 bits, this is efficient but uses more memory than the prefix set approach.

Interview Verdict: Accepted

This approach is optimal and demonstrates mastery of tries and bit manipulation, useful for advanced interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the greedy bit-by-bit approach is best as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code for large inputs
2. Greedy Bit-by-Bit with Prefix Set	O(n * log M)	O(n)	No	No	Code this for optimal solution
3. Trie-Based Bitwise Solution	O(n * log M)	O(n * log M)	No	No	Mention as alternative optimal solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then learn the greedy bit-by-bit approach, and finally the trie method for mastery.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach and its inefficiency.Step 3: Introduce the greedy bit-by-bit approach with prefix sets.Step 4: Optionally discuss the trie-based solution for completeness.Step 5: Code the greedy bit-by-bit approach and test.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, ability to optimize brute force, and knowledge of greedy and trie data structures.

Common Follow-ups

• What if numbers are very large? → Use 64-bit or adjust bit range accordingly.
• Can you find the pair of numbers that produce the max XOR? → Store indices or numbers during computation.

💡 Follow-ups test your ability to adapt the solution to variations and extract additional information beyond the maximum XOR value.

🔍

Pattern Recognition

When to Use

1) Problem asks for maximum XOR of two numbers; 2) Input is an array of integers; 3) Constraints allow bitwise operations; 4) Naive O(n^2) is too slow.

Signature Phrases

maximum XORtwo numbersbitwise XOR maximize

NOT This Pattern When

Problems that ask for sum or AND maximums, or those that do not involve bitwise XOR.

Similar Problems

Maximum XOR of Two Numbers in an Array - same core problemSingle Number - uses XOR propertiesFind Maximum XOR of Two Numbers in an Array - variant with similar approach

Practice

1. Given the following Trie implementation, after inserting the words ['cat', 'car', 'dog'], what is the value of node.isEnd after processing the last character of 'car' in the insert method?

easy

A. false, because 'car' shares prefix with 'cat' and 'dog'

B. true, but only if 'car' was inserted before 'cat'

C. false, because isEnd is only set after inserting all words

D. true, because 'car' is a complete inserted word

Solution

1. Step 1: Trace insertion of 'car'

   For each character 'c', 'a', 'r', nodes are created or reused. After last character 'r', node.isEnd is set to true.

2. Step 2: Confirm isEnd flag meaning

   isEnd marks the end of a complete word. Since 'car' was inserted, node.isEnd after 'r' is true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   isEnd is true after inserting 'car' [OK]

Hint: isEnd is set true after inserting each complete word [OK]

Common Mistakes:

• Assuming isEnd is false if prefix overlaps with other words

2. The following code attempts to count pairs with XOR less than a limit using a bitwise trie. Identify the line that contains a subtle bug that causes incorrect counts on some inputs.

medium

A. Line where node.count is incremented during insert

B. Line where the trie is not reset between queries causing accumulation

C. Line where result accumulates query(num, limit) before insert

D. Line where node is updated to node.children[bit] during insert

Solution

1. Step 1: Understand trie usage in counting pairs

   The trie accumulates counts of inserted numbers to query how many have XOR less than limit with current number.

2. Step 2: Identify the bug

   The code does not reset or clear the trie between different calls or test cases, causing counts to accumulate incorrectly if reused, leading to wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Not resetting trie causes stale counts to affect results [OK]

Hint: Trie must be fresh or cleared per independent query [OK]

Common Mistakes:

• Not resetting trie between test cases
• Incrementing count incorrectly
• Wrong bit traversal order

3. What is the time complexity of the optimal trie-based solution for finding shortest unique prefixes for n words each of maximum length m?

medium

A. O(n^2 * m) because each prefix is compared with all other words

B. O(n * m) because each word is inserted and traversed once in the trie

C. O(n * m^2) due to nested prefix checks during insertion

D. O(n * log n * m) because sorting is involved before trie insertion

Solution

1. Step 1: Identify operations per word

   Each word of length m is inserted into the trie once, updating frequency counts along the path.

2. Step 2: Analyze total complexity

   Insertion and prefix search both take O(m) per word, so total is O(n * m). No sorting or nested loops over words occur.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie insertion and search scale linearly with total characters [OK]

Hint: Trie operations scale with total characters, not pairwise comparisons [OK]

Common Mistakes:

• Confusing trie insertion with pairwise prefix checks
• Assuming sorting is required

4. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words

5. Suppose the MapSum data structure must support keys being inserted multiple times with updated values, and sum queries with an empty prefix should return the total sum of all keys. Which modification to the optimal trie-based solution correctly handles this?

hard

A. Return 0 immediately if prefix is empty, since no keys match empty prefix.

B. Use a separate hash map to sum all values and ignore trie sums for empty prefix queries.

C. Store and update a sum at the root node representing total sum of all keys, and return root.sum when prefix is empty.

D. Traverse all children of root node and sum their sums recursively on empty prefix queries.

Solution

1. Step 1: Understand empty prefix sum requirement

   Empty prefix means sum of all keys, so root node sum must represent total sum.

2. Step 2: Check how root sum is maintained

   Root.sum is updated on every insert with delta, so returning root.sum for empty prefix is correct and efficient.

3. Step 3: Evaluate other options

   Returning 0 is incorrect. Separate hash map duplicates data and is inefficient. Recursive traversal is costly and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Root sum stores total sum, perfect for empty prefix queries [OK]

Hint: Root node sum holds total sum for empty prefix queries [OK]

Common Mistakes:

• Returning 0 for empty prefix
• Not updating root sum on insert
• Using costly recursive sum on empty prefix