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;
}