XXOORR problem of july long challenge

help
, , ,
1

link to the question problem : XXOORR Problem - CodeChef

#include <iostream>
using namespace std;
typedef long long ll;

void solve()
{
	int n, k;
	cin >> n >> k;
	ll arr[n];
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	ll ans = 0;
	for (int i = 0; i < 32; i++)
	{
		int count = 0;
		for (int j = 0; j < n; j++)
		{
			if (arr[j])
			{
				if (arr[j] & 1)
					count++;
				arr[j] /= 2;

				
			}
		}
		ans += (count + k - 1) / k;
	}
	cout << ans << "\n";
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

In this solution , I was not able to understand this formula “(count + k - 1) / k”
Help me please !!

2

That formula is for partitioning count into blocks of size k.

Let’s say for one loop of i, count=5 and k=2. As per the question, atmost k indices can be operated upon in one go.

Then, no. of operations = (5+2-1)/2 = 3

So, to xor at one position for 5 numbers, I have to partition them in 3 blocks due to k-rule and then do the operations.

Hope I’m clear :slight_smile:

1 Like