# MINBITS - Editorial

Author: triggered_code
Tester: jay_1048576
Editorialist: iceknight1093

2594

# PREREQUISITES:

Greedy algorithms

# PROBLEM:

You’re given a large integer A in binary representation as a string of length N.
Find two binary strings B and C such that A = B-C, and the sum of counts of ones in B and C is minimized.

# EXPLANATION:

For convenience, this explanation will treat A, B, C as if they were reversed and 0-indexed, so that A_i corresponds to whether 2^i is set in A or not and so on.
In terms of implementation, this means you can reverse A, follow the solution below, then reverse B and C before printing them.

The problem essentially asks us to write A using the smallest number of powers of two, except we’re allowed to both add and subtract them (addition goes into B, subtraction goes into C).
However, there’s one small catch: B and C have to be of length N each, which means we can’t use larger powers.

Let’s first solve this without the restriction on length N — in the end, we can see how it comes into play.

If we weren’t allowed subtraction, the best we can do is obviously to just use all the bits set in the binary representation of A. So, let’s take this as our starting point and see how to reduce it.

The main power of subtraction is that it allows us to reduce a block of ones into two ones.
That is, we have

2^x + 2^{x+1} + 2^{x+2} + \ldots + 2^y = 2^{y+1} - 2^x

so we can replace y-x+1 additive powers of two with just two of them.
Of course, if x = y, this will replace one power of two with two of them, which is bad so we won’t do it.

This gives us a natural greedy solution:

• Let B = A and C be filled with zeros initially.
• Iterate from left to right, i.e from lower bits to higher bits; and find a maximum block of ones in B, say [L, R]. In particular, this means B_{L-1} = B_{R+1} = 0 must hold.
• If L = R, ignore it.
• Otherwise, set B_{R+1} = 1 and C_L = 1, since we’re replacing 2^L + \ldots + 2^R by 2^{R+1} - 2^L.

Note that iterating from lower to higher is important here because it allows us to further replace the bits we add to B.
For example, if A = \texttt{110110}, going from low to high we’d get:

• Step 1: B = \texttt{001110}, C = \texttt{100000}
• Step 2: B = \texttt{000001}, C = \texttt{101000}
whereas if we went high to low we’d get
• Step 1: B = \texttt{110001}, C = \texttt{000100}
• Step 2: B = \texttt{001001}, C = \texttt{100100}
which is not optimal.

This almost solves our problem in \mathcal{O}(N): the only thing that needs to be taken care of is the very end.
That is, notice that when replacing a block of ones, we need to use the next higher position.
However, if this block of ones forms a suffix of the string, the next position doesn’t exist, so we can’t perform this replacement.

It’s not hard to see that if a block of ones forms a suffix like this, then we have no choice: this suffix of ones must be set in B and none of them can be set in C.
So, we can simply delete the suffix of ones, solve normally for the remaining string (now without having to worry about edgecases!) and finally add the ones back in.

This way, we’ve solved the problem in \mathcal{O}(N).

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Author's code (C++)
#include <bits/stdc++.h>
#include <iostream>
#include <cassert>
#define int long long
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repr(i,n) for(int i = n-1; i >= 0; i--)
#define ff first
#define ss second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sz(x) (x).size()
#define all(x) x.begin(), x.end()
#define mems(x,a) memset((x), a, sizeof(x))
const char nl = '\n';
const int INF = LONG_MAX;
using namespace std;
using namespace __gnu_cxx;
// DEBUG TEMPLATE
void _print(char i){ cout<<i;}
void _print(string i){ cout<<i;}
void _print(float i){ cout<<i;}
void _print(int i){ cout<<i;}
void _print(double i){ cout<<i;}
void _print(bool i){ cout<<i;}
void _print(long double i){ cout<<i;}
void _print(){cout<<"\n";};
template<typename x,typename y> void _print(pair<x,y>&t){cout<<"{ ";_print(t.first);cout<<" , ";_print(t.second);cout<<" },";}
template<typename x> void _print(x &t){  cout<<"{ "; for(int i = 0;i < (int)t.size();i++){ _print(t[i]); if(i < (int) t.size() - 1) cout<<", "; } cout<<" }"; }
template<typename x,typename... y> void _print(x a,y... b){_print(a);if(sizeof...(b)) cout<<" , ";_print(b...);}
#define dbg(x...) cout<<"DEBUG : "<<#x<<" => ";_print(x);cout<<"\n";

vector<int> prime(int a, int b){
vector<bool> v(b+1, 1);
vector<int> ans;
rep(i,2,b+1){
if(v[i]){
for(int j = 2*i; j <= b; j += i){
v[j] = 0;
}
if(i >= a) {ans.pb(i);};
}
}
return ans;
}

bool subtract(string &a, string &b, string &c) {

int n = a.size();

/* Going from lsb to msb so we can ask for borrow */
for(int i = 0; i < n; i++){
int x = b[i]-'0';
int y = c[i]-'0';
int z = x-y;
if(z < 0){
int j = i;
while(j < n and b[j] == '0') j++;
if(j != n){
z = 1;
b[j--] = '0';
while(j >= i){
b[j--]  = '1';
}
}
else return false;
}

if(a[i] != '0'+z) return false;
}
return true;

}

bool test_case = 1;
void solve() {
int n;
cin >> n;
string a;
cin >> a;
reverse(a.begin(), a.end());
string b="",c="";
int cnt=0;
for(int i=0;i<n;i++)
{
if(a[i]=='1')
cnt++;
else
{
if(cnt>=1)
{
c+='1';
for(int j=0;j<cnt;j++)
{
b+='0';
c+='0';
}
b+='1';
}
else
{
b+='0';
c+='0';
}
cnt=0;
}
}
while(b.length()<n)
{
b+='1';
c+='0';
}
for(int i=0;i<n-1;i++)
{
if(b[i]=='1' && c[i+1]=='1')
{
b[i]='0';
c[i]='1';
c[i+1]='0';
}
else if(b[i+1]=='1' && c[i]=='1')
{
b[i]='1';
c[i]='0';
b[i+1]='0';
}
}
reverse(b.begin(), b.end());
reverse(c.begin(), c.end());

cout << b << '\n' << c << '\n';
}

signed main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt" , "r" , stdin) ;
freopen("output.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int T = 1;
if(test_case) cin>>T;

while( T-- ){
solve();
}

return 0;

}

Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
reverse(begin(s), end(s));

int suf = 0;
while (!s.empty()) {
if (s.back() == '1') s.pop_back();
else break;
++suf;
}

string b = s, c(n-suf, '0');
for (int i = 0; i < n-suf;) {
if (b[i] == '0') {++i; continue;}
int j = i;
while (j >= 0 and b[j] == '1') {
++j;
}
if (j-i > 1) {
c[i] = '1';
for (int k = i; k < j; ++k) b[k] = '0';
b[j] = '1';
}
i = j;
}
b += string(suf, '1'); reverse(begin(b), end(b));
c += string(suf, '0'); reverse(begin(c), end(c));
cout << b << '\n' << c << '\n';
}
}

1 Like

Can you please share any of the test case? Actually, I used exactly same logic as in above editorial, but still getting all wrong answers

So, it will be very kind of you to share any of the test cases so that I can check where my code failed.

Here is my submission btw. (I code in Rust language, but that should not matter)
https://www.codechef.com/viewsolution/95674113

can someone please provide the case where this might be failing
https://www.codechef.com/viewsolution/95675184

1 Like

found the case where i was failing 1101110111 ,

1 Like

For input

1
10
1101110111


My code is giving

1110001000
0000010001


Also, yes,
1110001000 – 0000010001 = 1101110111

And I don’t think less number of bits are possible

It should be correct answer I guess

1110000000
0000001001
this is the answer , you can verify by subtracting.

1 Like

@namanlp @pepethebuilder
In fact, if you read through the editorial you might notice that I’d already included a failing case there The string 110110 (or rather its reverse, 011011) can be solved with 3 ones.

2 Likes

Can anyone tell me how you get the intuition for this problem? Any prerequisite before solving this question?

Ohhh

Yeah, I see it now, what was wrong.

Thanks a lot for explaining @iceknight1093 and @pepethebuilder

Maybe, practice more and more bit manipulation questions of lower level first.

Also, you must know about truth tables, and bit manipulation operations like or, xor, and, not, left shift, right shift etc.

Practice is the key