Problem Link:
Clash Wildcard 2022
Practice
Problem:
We are given a string containing only 1’s and 0’s. Our task is to find minimum operations required on to convert the given string to a string where 1’s and 0’s are in alternate positions.
An operation can be of two types:
- Swap any two of character of the string.
- Or replace any character with the other.
Approach:
We can notice that there are only two possible arrangements that satisfy the problem statement: 010101… or 101010…
Let’s go through both of these arrangements:
In each case let’s count the number of bottles and packets which are not in the alternate positions. Let’s denote these numbers as x and y.
Then it is obvious that the min(x, y) pairs of packet and bottles need to be swapped and the rest should be replaced.
In other words, the result for an arrangement is min(x, y) + ( max(x, y) - min(x, y) ) => max(x, y).
Finally, the answer for the question will be minimum of the results of both the arrangements.
Setter's Solution (C++)
#include <bits/stdc++.h>
#include <iostream>
using ll = long long int;
using namespace std;
int main()
{
ll t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
string s;
cin >> s;
ll a = 0, b = 0, c = 0, d = 0;
for (int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
if (s[i] == '0')
{
a++;
}
else
{
b++;
}
}
else
{
if (s[i] == '0')
{
c++;
}
else
{
d++;
}
}
}
ll x = max(b, c);
ll y = max(a, d);
ll z = min(x, y);
cout << z << endl;
}
return 0;
}