How to solve this question?

#1

821×914 28.8 KB

#2

Should I try to give you hints or tell the complete solution?

#3

Complete solution with explanation.

#4

Any number ‘a’, can have a total of log(a) possible values after these operations, as we divide by 2 every time.

Therefore, we can store all these values for all these numbers, which will take O(n*log(a)) space and time.

For, every number store all the possible ways in which you can reach that number.
like for the given input

4 4
1 1 1 4

Store,

0 -> 1, 1, 1, 3  // one move for each of the ones and 3 for the four
1 -> 0, 0, 0, 2  // the ones are already = 1, so 0 moves for them and 2 moves for the four
3 -> // empty, not possible
4 -> 0  // only four can become a 4, and that in 0 moves

Now, for each number if the size of vector corresponding to that number is greater than ‘n’, then we consider it as a possible and and take the minimum of all such possible answers.

#5

But multiple values of K are possible.

1 Like
#6

Yeah, so??? What is the issue?

#7

You are considering only the cases where k=n.

1 Like
#8

Ohh, okay replace n with k in my above tutorial, it doesn’t really matter.

Actually the example was 4 4, so I forgot that k was 4 not n.

#9

It won’t be an efficient solution and may lead to TLE because you are calculating more than than n values for each n.

#10

Noo, that is not what I am doing.

I am just iterating over all the possible numbers (of the order of O(nlog(n))), and determining in O(1) the answer part.

#11

It would be more clear if you provide the code in c++.

#12

Yes, okay, please share the link to the question. I will code there and get back to you.

#14 
#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 1e5 + 10;
vector<int> arr[N];

int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int t;
		cin >> t;
		int cnt = 0;
		while (t) {
			arr[t].push_back(cnt);
			cnt++;
			t /= 2;
		}
	}

	int ans = INF;
	for (int i = 1; i < N; ++i) {
		if (arr[i].size() >= k) {
			sort(arr[i].begin(), arr[i].end());
			int s = 0;
			for (int j = 0; j < k; ++j) {
				s += arr[i][j];
			}
			ans = min(ans, s);
		}
	}
	cout << ans;
	return 0;
}