Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

Rafiq loves to play with dominoes. On his birthday his father gifted him ‘N’ piles of dominoes, where each pile contains a positive number of dominoes stacked above.

Rafiq loves to play with piles if they are of equal heights, so his father decides to make changes to the piles. His father wonders for each consecutive window of length ‘K’ what is the minimum cost to make them all of the equal height. Hence his father wants to calculate the cost for each window.

The cost for removing and adding one domino on any pile is one unit.

Determine what is the cost to make all elements equal in a window of size 'K', for all windows of size 'K' in an 'N'-sized array/list 'heights'.

Detailed explanation

```
1 <= T <= 10
1 <= N <= 10000
1 <= K <= N
1 <= height[i] <= 10^5
where 'T' is the number of test cases, 'N' is the number of piles, 'K' is the size of the window as discussed above and 'height[i]' represents the height of each pile.
Time limit: 1 sec
```

```
1
6 2
2 4 1 1 2 3
```

```
2 3 0 1 1
```

```
All the windows or subarray of size 2 are [2,4] , [4,1] , [1,1] , [1,2] , [2,3]. The cost of each subarray is 2,3,0,1,1.
```

```
1
6 3
3 1 1 1 4 4
```

```
2 0 3 3
```

```
All the windows or subarray of size 3 are [3,1,1] , [1,1,1] , [1,1,4] , [1,4,4] , [2,3]. The cost of each subarray is 2,0,3,3.
```