Discussion on Xor and Sum Challenge

4 years ago+ 0 comments

here is a C++ solution that uses only 32 and 64 bit integers, and passes all test cases in O(lg a + lg b) time and space (took me about 4 hours of debugging, so the code is a bit messy, but I finally got it to work, and it runs very fast). No recursion or dynamic programming is used.

The basic idea is that only the first approximately lg a terms in the sum require any actual XOR to be done; for the rest of the terms, a and b are "decoupled" and XOR is equivalent to addition, so that part of the sum can be computed in O(1) time.

The XOR in the first lg a terms can be done by "sliding" b through a, and for each bit in a (as well as the zeros padding a from above), we can count the number of zeros and ones that will "hit" that bit in O(1) time per bit, provided that we precompute the number of ones and zeros in b, which takes O(lg b) time.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::vector;

constexpr unsigned mod=1000000007U;
constexpr unsigned top=314159U;
constexpr unsigned powtop=348880127U; // 2**(top+1) % mod

vector<unsigned> powers(int n){
  vector<unsigned> p;
  p.reserve(n);
  unsigned x=1;
  p.push_back(x);
  for(int i=1;i<n;++i){
    x=(x<<1)%mod;
    p.push_back(x);
  }
  return p;
}

inline void increment(unsigned &x, unsigned y){
  x=(x+y)%mod;
}

unsigned solve(const vector<bool> &a, const vector<bool> &b){
  const int na=a.size(), nb=b.size();
  vector<unsigned> p{powers(na+nb)};  
  unsigned sum=0;
  vector<unsigned> ones(nb,0), zeros(nb,0);
  zeros[0]=!b[0];
  ones[0]=b[0];
  for(int i=1;i<nb;++i){
    ones[i]=ones[i-1]+b[i];
    zeros[i]=zeros[i-1]+(!b[i]);
  }
  for(int i=na+nb-2, j=nb-1, k=1; i>=na; --i){
    unsigned long add=p[i];
    unsigned nones=ones[j]-(j>=k?ones[j-k] : 0);
    add=(add*nones)%mod;
    increment(sum,static_cast<unsigned>(add));
    if(i<nb) --j;
    if(k<na) ++k;
  }
  for(int i=na-1;i!=-1;--i){
    unsigned long add=p[i];
    unsigned times=0;
    unsigned nones=i<nb? ones[i]:ones.back();
    unsigned nzeros=i<nb? zeros[i]:zeros.back();
    if(a[i]){
      times=nzeros+na-1-i;
      if(i>nb-1) times+=i-(nb-1);
    }else if(i<nb-1) times=nones;
    else times=ones.back();
    add=(add*times)%mod;
    increment(sum,static_cast<unsigned>(add));
  }
  unsigned aval=0,bval=0;
  for(int i=0;i<na;++i){
    if(a[i]) increment(aval,p[i]);
  }
  for(int i=0;i<nb;++i){
    if(b[i]) increment(bval,p[i]);
  }
  unsigned long temp1=top-na+1;
  temp1=(temp1*aval)%mod;
  increment(sum,static_cast<unsigned>(temp1));
  unsigned long temp2=powtop;
  temp2+=mod-p[na];
  temp2=(temp2*bval)%mod;
  increment(sum,static_cast<unsigned>(temp2));
  return sum;
}


void input(){
  string sa,sb;
  std::cin >> sa >> sb;
  const int na=sa.size(), nb=sb.size();
  vector<bool> a(na,0), b(nb,0);
  for(int i=0;i<na;++i) a[na-i-1]=(sa[i]=='1');
  for(int i=0;i<nb;++i) b[nb-i-1]=(sb[i]=='1');
  std::cout << solve(a,b) << '\n';
}

int main(){
  input();
}