Game of Dominoes

Moderate

0/80

Average time to solve is 30m

Contributed by

4 upvotes

Asked in companies

Problem statement

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 ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ i.e., length of the pile and ‘K’ size of the window.

The next line of each test case contains 'N' numbers a1, a2, a3... aN denoting the initial height of each pile.

Output Format:

For each test case, output the minimum cost for each window.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

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

Sample Input 1:

1
6 2
2 4 1 1 2 3

Sample Output 1:

2 3 0 1 1

Explanation of sample input 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.

Sample Input 2:

1
6 3
3 1 1 1 4 4

Sample Output 2:

2 0 3 3

Explanation of sample input 2:

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.

Console