SDE - Intern

Step 1: Compute Subtree Sums

Perform a Post-order Traversal (DFS) to calculate the sum of each subtree.

Let S(u) be the sum of the subtree rooted at u.

S(u)=arr[u]+∑S(v) for all children v of u.

Store these sums in an array.

Step 2: Define the "Non-Overlapping" Constraint

Two subtrees rooted at u and v are non-overlapping if:

v is not in the subtree of u.

u is not in the subtree of v.
To handle this efficiently, we use the property that for any edge (u, parent), if we "cut" it, we split the tree into two disjoint components: the subtree at u and the rest of the tree.

Step 3: Two-Pass DFS with a Trie

The core challenge is finding the max XOR between a subtree and any other subtree that is not its descendant/ancestor.

First Pass (Pre-order): As you traverse down, the "already processed" subtrees in other branches are valid candidates for XOR.

The Trie Strategy:

Maintain a Binary Trie to store subtree sums encountered so far.

For each node u, we want to find a value X in the Trie that maximizes S(u)⊕X.

Standard Trie Max-XOR logic: For each bit of S(u) from 31 down to 0, try to move to the branch representing the opposite bit.

Step 4: Global Maximum

Since the "other" subtree could be anywhere else, we actually need to track the maximum possible XOR found by either:

A subtree in the current path vs. a subtree in a previously visited sibling's branch.

A subtree vs. the remaining part of the tree (TotalSum−S(u)).

Step 1: Understand the Target State

When you perform A[j]=A[i]∣A[j] for all j, the new value of every element will at least contain all the bits that were set in A[i]. If you perform this multiple times using different indices i1​,i2​,..., eventually every element in the array will become the Bitwise OR of all elements in the original array (let's call this target).
Step 2: Check for 0 Operations

First, check if all elements in the array are already equal. If they are, the answer is 0.
Step 3: Check for 1 Operation

Is it possible to make all elements equal in one step? This happens if there exists an index i such that after picking it, every A[j]∣A[i] becomes the same value.

This is only possible if for some i, A[j]∣A[i] equals a constant for all j.

Specifically, that constant must be the target (the OR of the entire array).

Condition: If there exists an A[i] such that for all j, A[j]∣A[i]==target, then the answer is 1.

Step 4: Check for 2 Operations

If no single element can "pull" all others to the target value, can two elements do it?

In bitwise OR operations, picking two indices i and k sequentially is equivalent to picking one element that is (A[i]∣A[k]).

Since the maximum value is small (5000, which is <213), we can use a Bitmask BFS or a greedy check.

However, a key observation: For most cases where 0 or 1 doesn't work, 2 operations will suffice. You pick one element to cover some bits, and another to cover the remaining bits.

Step 1: Initialize Search Range

Set two pointers, low = 0 and high = n - 1. Calculate the middle index mid = low + (high - low) / 2. The goal is to use the "slope" at mid to decide which direction to move.
Step 2: Compare Mid with its Right Neighbor

Compare arr[mid] with arr[mid + 1]:

If arr[mid] < arr[mid + 1]: You are on an upward slope. This means there must be a peak to the right of mid. Therefore, move the search range to the right by setting low = mid + 1.

If arr[mid] > arr[mid + 1]: You are either on a downward slope or at a peak. This means a peak exists at mid or to its left. Move the search range to the left by setting high = mid.

Step 3: Converge on the Peak

Repeat the process until low == high. At this point, the pointers will have converged on a peak element. Return low (or high). Because we always move toward the "higher" side, we are guaranteed to find a local maximum.

Step 1: Define the TrieNode Structure

Each node represents a single character. It needs:

An array (or hash map) of pointers to its children (size 26 for lowercase English letters).

A boolean flag isEndOfWord to mark the completion of a valid word.

Step 2: Implement the Core Logic

Insert: Iterate through the word character by character. If a child for the current character doesn't exist, create a new node. Move to that child. Mark the last node's isEndOfWord as true.

Search/StartsWith: Navigate the tree following the characters of the input string. If at any point a pointer is NULL, the word/prefix doesn't exist. For Search, also check if the final node has isEndOfWord == true.