Algorithm

D1. Equalizing by Division (easy version)
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1213/problem/D1
input
standard input
output
standard output

The only difference between easy and hard versions is the number of elements in the array.

You are given an array a� consisting of n� integers. In one move you can choose any ai�� and divide it by 22 rounding down (in other words, in one move you can set ai:=⌊ai2⌋��:=⌊��2⌋).

You can perform such an operation any (possibly, zero) number of times with any ai��.

Your task is to calculate the minimum possible number of operations required to obtain at least k� equal numbers in the array.

Don't forget that it is possible to have ai=0��=0 after some operations, thus the answer always exists.

Input

The first line of the input contains two integers n� and k� (1≤k≤n≤501≤�≤�≤50) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤2⋅1051≤��≤2⋅105), where ai�� is the i�-th element of a�.

Output

Print one integer — the minimum possible number of operations required to obtain at least k� equal numbers in the array.

Examples
input
Copy
5 3
1 2 2 4 5
output
Copy
1
input
Copy
5 3
1 2 3 4 5
output
Copy
2
input
Copy
5 3
1 2 3 3 3
output
Copy
0

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 10;
int n, k, a[N], fr[N], frp[N];

int main() {
#ifndef ONLINE_JUDGE
	freopen("in", "r", stdin);
#endif

	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; ++i)
		scanf("%d", a + i);
	sort(a, a + n);

	int res = 1e9;
	for(int i = 0; i < n; ++i) {
		int cur = a[i], cnt = 0;
		while(cur >= 0) {
			++fr[cur];
			frp[cur] += cnt;
			if(fr[cur] >= k)
				res = min(res, frp[cur]);
			if(cur == 0)
				break;
			cur /= 2;
			++cnt;
		}
	}

	printf("%d\n", res);

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5 3
1 2 2 4 5

Output

x
–
+
cmd
1
Advertisements

Demonstration

Codeforcess Solution D1. Equalizing by Division (easy version)-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+