In this HackerEarth Partitioning problem solution, we have given a binary string of length N(containing only 0's and 1's) and two integers C, P. 

Put exactly 3 dividers in the string so that the integer between the first and second divider (it's decimal equivalent) is C and that between the second and third divider is P(it's decimal equivalent). There cannot be more than 25 digits in the binary representation of P or C(inclusive of preceding or leading 0's). Find the number of ways to put these dividers.


HackerEarth Partitioning problem solution


HackerEarth Partitioning problem solution.

#include <bits/stdc++.h>
using namespace std;
string s;
long long value(int b,int c)
{
long long val=0,l=1;
for(int i=c;i>=b;i--)
{
if(s[i]=='1')
{
val+=l;
}
l*=2;
}
return val;
}
int main()
{
freopen("input1.txt","r",stdin);
freopen("output1.txt","wb",stdout);
long long int c,p;
cin>>s;
cin>>c>>p;
int len=s.length();
long long ans=0;
for(int i=0;i<len-2;i++)//partition 2 after ith position
{
int cl=0,cr=0;
//cout<<i<<" ";
for(int j=max(0,i-25+1);j<=i;j++)
{
long long a=value(j,i);
if(a==c)
cl++;
}
//cout<<"OK";
for(int j=i+1;j<=min(len-1,i+25);j++)
{
long long a=value(i+1,j);
if(a==p)
cr++;
}
ans+=cr*cl;
// cout<<ans<<endl;
}
cout<<ans<<endl;
}


Second solution

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define irep(i,a,b) for (int i=a;i>=b;i--)
#define pii pair <int, int>
#define pll pair <ll,ll>

using namespace std;
const int ma = 1e5+5;

ll c,p;
string s;
int count_zero(ll c)
{
int ans=0;
while(c%2==0)
{
ans++;
c/=2;
}
return ans;

}

int solve(int i)
{
int ans=0;
ll fp=0,fc=0,tp=1;
int zero = count_zero(c);
int e = max(0,i-24);
while(i>=e)
{
fp+=(s[i]-'0')*tp;
tp*=2;
i--;
if(fp==p)
break;
}

if(i<0 or fp!=p)
return 0;

int idx = i;
while(idx>=0 and s[idx]=='0')
idx--;

if(idx<0)
return 0;

if(zero<=i-idx)
i = idx+zero;

e = max(0,i-24);
tp=1;
bool f=false;
while(i>=e)
{
fc += (s[i]-'0')*tp;
tp*=2;
i--;
if(!f)
{
if(fc==c)
{
ans++;
f=true;
}
}
else
{
if(fc==c)
ans++;
else
break;
}
}
return ans;
}
int main(int argc, char* argv[])
{
if(argc == 2 or argc == 3)
freopen(argv[1], "r", stdin);
if(argc == 3)
freopen(argv[2], "w", stdout);
ios::sync_with_stdio(false);

cin>>s;
for(int i=0;i<s.length();i++)
{
assert(s[i]>='0' and s[i]<='1');
}
ll po = 1<<25-1;
cin>>c>>p;
assert(c>=1 and c<=po);
assert(p>=1 and p<=po);
int i = s.size()-1;
ll ans=0;
while(i>=0)
{
ans += solve(i);
i--;
}
cout<<ans<<endl;
return 0;
}