Xor and sum HackerRank problem

1

I am unable to solve the problem please help me figure out the
errors in my code

Problem link: Xor and Sum | HackerRank

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mod=1000000007,sum=0,p=0,q=0,i,err=0,n;
ll power(ll base, ll index)
{
    ll res=1;
    base=base%mod;
    while(index>0)
    {
        if(index%2==1)
        {
            res=(res*base)%mod;
        }
        base=(base*base)%mod;
        index=index/2;
    }
    return res;
}
int main()
{
    string a,b;
    cin>>a>>b;
    n=a.length();
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    i=0;
    for(char x:a)
    {
        p=p+power(2,i)*(x-'0');
        i++;
    }
    i=0;
    for(char x:b)
    {
        q=q+power(2,i)*(x-'0');
        i++;
    }
    while(n--)
    {
        err=err+(p&q)%mod;
        q=q*2;
    }
    sum=sum+((314160)%mod*p)%mod+((power(2,314160)-1)%mod*2)%mod-(2*(err%mod))%mod;
    cout<<sum%mod<<endl;
    return 0;
}
2

Can you explain your approach, and in the while loop of n-- if n=10^5 then q would be multiplied by 2^10^5 , which will surely make it to overflow until q is not equal to 0

3

You can not do this way, especially in C++. long long hold only upto 64\ bits and here integer A and B can have upto 10^5 bits. So it will overflow.

You can form result bit by bit:

  • First of all, left shift means inserting zero at right most position of binary rep.
    i.e b = '10111', so (b<<1) = '101110', (b<<2) = '1011100'

  • 1\oplus0 = 1,\ \ 1\oplus0 = 1,\ \ 1\oplus0 = 1,\ \ 1\oplus0 = 1 where \oplus means xor

  • Let define C_k for which \ C_k= B[k] \ if \ k>=0 \ else\ C_k=0

  • After some analysis you will notice that answer for i^{th} bit of A will be
    \ 2^i*\sum_{j=0}^{314159} A[i]\oplus C_{i-j}

  • So final answer will be

    ans = \sum\limits_{i=0}^{max(n,m+314159)}(2^i*\sum\limits_{j=0}^{314159}A[i]\oplus C_{i-j})

Naive implementation of above will be TLE , so can be done efficiently using the Sliding window concept or Prefix sum by maintaining count of zeros and ones for window of length 314159.

Note that Indexing in the binary representation is done from right to left.

Code 
def xorAndSum(a, b):
    #
    # each bit of a will be coupled with each bit of b for 314159 shifts
    # in other words, a(i) will be coupled with all bits of b(i,i-314159)
    # so we can use sliding window concept to maintain the count of ones and zeros
    # 
    # left shift means inserting 0 to right side 
    # 
    a = [int(i) for i in a[::-1]]
    b = [int(i) for i in b[::-1]]
    n = max(len(a),len(b)+314159)
    a+=[0]*(n-len(a))
    b+=[0]*(n-len(b))
    zero = 314159
    one = 0
    res = 0
    mod = int(1e9+7)
    for i in range(n):
        zero+=b[i]==0
        one+=b[i]==1
        if a[i]==1:
            res+=zero*pow(2,i,mod)%mod
        else:
            res+=one*pow(2,i,mod)%mod
        res%=mod
        if i>=314159:
            one-=b[i-314159]==1
            zero-=b[i-314159]==0
        else:
            zero-=1
    return res
2 Likes