Xor and Sum Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Xor and Sum
  5. Discussions

Xor and Sum

  • dehaka
     + 0 comments

    no idea how on earth people are doing it in 4 few lines with what seems to be the brute force method

    this method is O(414159 + b.size()), and works for ANY bitwise operator not just XOR

    long xorAndSum(string a, string b) {
    a.insert(0, 414159 - a.size(), '0');
    long result = 0, mod = 1000000007;
    vector<long> twoPower = { 1 }, aPartial = {0, a.back()-'0'};
    for (int i = 1; i < 414159; i++) {
        twoPower.push_back((2 * twoPower.back()) % mod);
        aPartial.push_back((aPartial.back() + (a[414158 - i] - '0') * twoPower.back()) % mod);
    }
    for (int i=0; i <= 314159; i++) result = (result + aPartial[i] + aPartial[414159] - aPartial[i+b.size()]) % mod;
    vector<vector<long>> cache = { {0, 0} };
    for (int i = 0; i <= 314159; i++) {
        cache[0][0] = (cache[0][0] + ((a[414158 - i] - '0') ^ 0) * twoPower[i]) % mod;
        cache[0][1] = (cache[0][1] + ((a[414158 - i] - '0') ^ 1) * twoPower[i]) % mod;
    }
    for (int i = 0; i < b.size(); i++) {
        result = (result + cache[i][b[b.size() - 1 - i] - '0']) % mod;
        long zero = (cache[i][0] - ((a[414158 - i] - '0') ^ 0) * twoPower[i]) % mod;
        long one = (cache[i][1] - ((a[414158-i] - '0') ^ 1) * twoPower[i] + twoPower[i+314160]) % mod;
        cache.push_back({zero, one});
    }
    return (result + mod) % mod;
}