SDE - 1

Algorithm:

Step 1: For each element in the array, maintain two helper arrays: prefix (stores leftmost occurrence of a set bit) and suffix (stores rightmost occurrence of a set bit).
Step 2: Traverse the array to populate the prefix and suffix arrays.
Step 3: For each element, determine the number of valid subarrays using the prefix and suffix arrays.
Step 4: Accumulate the count of valid subarrays.

Algorithm :

Step 1: Parse each login record to extract the user, time, and date.
Step 2: Use maps to store user login counts based on valid date entries.
Step 3: For each user, increment the login count for the specific date if the record is valid.

Algorithm :

Step 1: Apply merge sort to the array, splitting it into subarrays.
Step 2: Count inversions during the merge step by comparing left and right subarrays. If an element from the left is greater than the right, it forms an inversion.
Step 3: Accumulate inversion counts from each merge operation.

Algorithm :

Step 1: Use two DFS traversals:
First DFS (dfs1) computes how many reversals are needed to make the tree rooted at node 0 unidirectional.
Second DFS (dfs2) calculates the minimum reversals needed for the entire tree by considering parent-child relationships and adjusting based on the direction of each edge.
Step 2: Return the minimum reversal count.

Approach

The approach is based on Dynamic Programming (DP).

First, a check is made to see if zero is greater than one. If this is the case, we call the same function but swap zero and one. This is because the types of characters (0 or 1) are interchangeable, and we want to ensure that zero is less than or equal to one for the following steps.

Next, we initialize a DP array dp of size high + 1, where dp[i] represents the number of "good strings" of length i that we can build. We set dp[0] = 1, as there is one way to create a string of length zero: an empty string.

We then iterate over i from 1 to high:

If i is greater than or equal to one, we set dp[i] to dp[i - zero] + dp[i - one]. This update signifies the ways to build strings of length i by appending a '0' to strings of length i - zero and a '1' to strings of length i - one, while adhering to the maximum consecutive counts.

If i is less than one but greater than or equal to zero, we set dp[i] to dp[i - zero]. This optimization is made because, after some iterations, i will always be greater than zero, and execution will not fall into this branch again.

If i is greater than or equal to low, we update our answer ans by adding dp[i]. Strings of length i contribute to our final count of good strings.

Finally, we return ans modulo MOD, as the problem asks for the answer modulo 109+710^9 + 7109+7.

Tip 1: Thoroughly revise DBMS
Tip 2: Practice SQL frequently.

Tip 1: Just solve it with the right intuition.
Tip 2: Solve all the puzzles available online.

Tip 1: Practice all puzzles.
Tip 2: Always give a logical answer.

Tip 1: Do read and implement OS.
Tip 2: Explain the answers in brief.