Problem : Removing minimum element from every subarray and count all such subarrays whose sum is divisible by **K**.

Think over another simple problem of similar kind, without removing any element. That is count how many subarrays’ sum is divisible by **K**. Then only move forward!

Considering some subarray from some index **L** to some index **R** where **L** < **R** (strictly less). Suppose minimum element of this subarray is at index **M** where **L <= M** and **M <= R** . It is easy to observe that for the left subarray **([L,M-1])** and the right subarray **([M+1,R ])** will have their own minimum element independent of index **M**. Thus after solving the problem for any subarray, we have to divide the problem in 2 different independent parts. This will be done with the help of recursion (Divide & Conquer).

Now the issue is how to solve the problem for a particular subarray. In a subarray $[L,R]$ with minimum at index $M$, we have to consider these subarrays:-

- Subarrays starting at index
**M**and going towards**R** - Subarrays starting at index
**M**and going towards**L** - Subarrays starting at some index
**x**less than M and completing at some index**y**greater than M. That is**L<=x<M<y<=R**.

Lets solve them one by one :-

- Remove the element at index
**M**(bcoz v have to discard element at index**M**), that is start with element at index**M+1**and traverse towards**R**adding elements one by one and checking at each step whether the sum is divisible by**K**or not. (can be done using modulo**%**operator). - Similarly, Remove the element at index
**M**, that is start with element at index**M-1**and traverse towards**L**adding elements one by one and checking at each step whether the sum is divisible by**K**or not. (can be done using modulo**%**operator). - This one is interesting. For finding these kind of subarrays, we could take help from the above two subarrays. Lets assume that there are
**u**subarrays starting at index**M**and going towards index**L**having reminder**r**(when divided with**K**). Also say there are**v**subarrays starting at index**M**and going towards index**R**having reminder**K-r**. Each pair of these subarray also forms a subarray eligible to be counted. (Why ? If you merge two subarrays having reminder $2$ and $K-2$, the merged subarray will have reminder**0**). Thus the answer would be**u*v**.

After solving for a subarray, one has to call two recursion calls. The time complexity of this problem would be like **Quicksort** where u divide the subrray into 2 segments and the extra time other than recursion is **O(n)** (bcoz u have to traverse each segment to save reminders into some map).

U will have to read the solution now after understanding these key points!

The link to the solution is

If u have any queries or doubts, feel free to comment or contact our team!