SDE - 1

Step 1: The Binary Analogy

Think of the characters as powers of 2.

'a' = 20=1

'b' = 21=2

'c' = 22=4

... and so on.

Merging two 'a's (1+1) gives one 'b' (2). Merging two 'b's (2+2) gives one 'c' (4). Since we want the lexicographically largest string, we want the highest possible characters at the beginning of the string. This is exactly how a binary number works: the most significant bits represent the highest powers of 2.
Step 2: Convert n to Binary

Because you start with n 'a's, your "total value" is n×20. To find the largest characters you can form, represent n in base 2.

Each bit i that is set to 1 in the binary representation of n corresponds to one character at the i-th position of the alphabet.

Example: If n=13, the binary is 11012​.

23 (8), 22 (4), and 20 (1).

These correspond to the 4th, 3rd, and 1st letters: d, c, and a.

Step 3: Construct the String

To make the string lexicographically largest, sort these characters in descending order.

Using the n=13 example: The characters are d, c, a.

The result is "dca".

Since n≤109 and 229<109<230, the maximum character you can reach is roughly the 30th letter. However, the English alphabet only has 26 letters.

Step 4: Handling the 'z' Limit

The alphabet caps at 'z' (the 26th letter). If your binary representation suggests characters beyond 'z' (bits i≥25):

Any value equivalent to 225 or higher must be converted back into 'z's.

Value of 'z' = 225.

Number of 'z's = ⌊n/225⌋.

The remainder (n(mod225)) is then converted to binary to find the characters from 'y' down to 'a'.

This problem is a mathematical optimization task often categorized as a "Greedy" or "Brute Force with Observation" problem. The core challenge is deciding when to use the two-element increment (cost2) versus the single-element increment (cost1).
Problem Statement

Title: Minimum Cost to Equalize Array

You are given an array nums and two cost values: cost1 (cost to increment one element) and cost2 (cost to increment two distinct elements). Find the minimum cost to make all elements in the array equal.

Operation 1: nums[i] += 1 for cost1.

Operation 2: nums[i] += 1 and nums[j] += 1 for cost2.

Constraint: The target value must be at least the current maximum element in the array.

Solution in Steps
Step 1: Determine the Search Range for the Target

Let max_val be the maximum element in the original array. The final equalized value T must be ≥max_val. Interestingly, the optimal T isn't always max_val; increasing T further might allow more "pairs" to be used (if cost2 is cheap), potentially lowering the total cost. Usually, checking T up to 2×max_val is sufficient.
Step 2: Calculate Total Increments Needed

For a fixed target T:

Calculate the gap for each element: gapi​=T−nums[i].

Find the total sum of gaps: S=∑gapi​.

Identify the maximum gap: Gmax​=max(gapi​).

Step 3: Calculate Minimum Cost for Target T

The cost calculation depends on the relationship between cost1 and cost2:

Case A: 2×cost1≤cost2
It is always cheaper to use cost1 twice than cost2 once.
Cost =S×cost1.

Case B: cost2<2×cost1
We want to use cost2 as much as possible.

Subcase 1 (Restricted by Gmax​): If the largest gap is more than all other gaps combined (Gmax​>S−Gmax​), we can only pair other elements with the largest gap.

Pairs possible: P=S−Gmax​.

Remaining single increments: R=Gmax​−P.

Cost =(P×cost2)+(R×cost1).

Subcase 2 (Balanced Gaps): If Gmax​≤S−Gmax​, we can pair almost everything.

If S is even: Pairs =S/2. Cost =(S/2)×cost2.

If S is odd: Pairs =(S−1)/2. Cost =((S−1)/2×cost2)+cost1.

Step 4: Iterate and Compare

Loop through possible values of T (from max_val to 2×max_val), calculate the cost for each using the logic above, and keep track of the global minimum. Apply modulo 109+7 to the final result.

Step 1: Build an Adjacency List with Directional Metadata

Since the input connections give us directed edges, we need a way to traverse the tree in any direction while still knowing which way the original road pointed.

Represent the graph as an adjacency list where each entry stores the neighbor and a boolean (or integer) indicating if the edge is original (pointing away from 0) or artificial (pointing toward 0).

Example: For [a, b], add (b, true) to adj[a] and (a, false) to adj[b].

Step 2: Perform a Traversal (DFS or BFS) starting from City 0

Start a traversal from the capital (City 0). Because we are moving away from the root to visit all nodes:

If we encounter an original edge (a -> b), it means the road is currently pointing away from the capital. We must reverse it to allow city b to reach a (and eventually 0).

If we encounter an artificial edge (b -> a), it means the road is already pointing toward the capital. No change is needed.

Step 3: Accumulate the Count

Every time you traverse an "original" edge during your DFS/BFS, increment a counter. Since it's a tree, you will visit every edge exactly once. The final count is the minimum number of reorientations required.

Step 1: Initialize Boundary Pointers

Place two pointers, left at the beginning (0) and right at the end (n−1) of the array. Also, maintain two variables, left_max and right_max, initialized to 0, to track the highest bars encountered from both directions.
Step 2: Iterate and Compare Heights

While left < right:

Compare height[left] and height[right].

If height[left] < height[right]: The water level is bottlenecked by the left side.

If height[left] >= left_max, update left_max.

Else, add left_max - height[left] to your total trapped water.

Move the left pointer forward.

Else (height[right] <= height[left]): The water level is bottlenecked by the right side.

If height[right] >= right_max, update right_max.

Else, add right_max - height[right] to your total trapped water.

Move the right pointer backwards.

Step 3: Return Total

Once the pointers meet, the accumulated sum represents the total volume of trapped water. This approach ensures O(N) time complexity and O(1) space complexity.