'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Game of Dominoes

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in companies
OlaInfosysProcol

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 )
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.
Full screen
Console