Roy and Array
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Time Limit: 1.0 s
Memory Limit: 256.0 MB
Description
You are given an Array A[] and the length of the array is N and also given an integer K. You need to rearrange this array such that,
for each i from ,\(1 <= i <= NK+1\),
\(S_i= A_i + A_{i+1} + A_{i+2} + ... + A_{i+(K1)}\)
and \(S_i\) is equal for all i.
for example, \(A [] \)= {1,2,1} and K=2.
\(S_1= A_1 + A_2 = 1 + 2 = 3\)
\(S_2= A_2 + A_3 = 2 + 1 = 3\)
Since, \(S_1 = S_2\), it's a beautiful array.
Before rearrange this array, you can do following operation:
 Choose indices i, \(1 <= i <= N\), and changes its value any positive integer d. (Ex. A [i] = d).
Input
First Line Contain T, the number of test cases.
In each test case, First line two positive integers N and K.
In each test case, Second line an array A [] and the length of the array is N.
\(1 <= T <= 10^5\)
\(1 <= N <= 3 * 10^5\)
\(1 <= K <= N\)
\(1 <= A[] <= 10^9\)
It's guranteed that sum of N overall test case doesn't exceed \(3 * 10^5\).
Output
In each test case, print minimum operation required to make array beautiful.
Sample
Input  Output 



First Test case, Array A = {1,2,3,4}.
if we change index 3 with value 2, then array A = {1,2,2,4}.
if we change index 4 with value 1, then array A = {1,2,2,1}.
Now array A = {1,2,2,1}.
if we rearrange Array A = {2, 1, 2, 1}.
\(S_1 = 2 + 1 = 3\)
\(S_2 = 1 + 2 = 3\)
\(S_3 = 2 + 1 = 3\)
Since \(S_1 = S_2 = S_3 \), array is beautiful.
minimum operation required is 2.
Brain Booster #4
 Status
 Done
 Rule
 ACM/ICPC
 Problem
 9
 Start at
 20240714 15:30
 End at
 20240714 19:00
 Duration
 3.5 hour(s)
 Host
 Partic.
 89