HackerRank Xor and Sum Problem Solution

In this post, we will solve HackerRank Xor and Sum Problem Solution.

You are given two positive integers a and b in binary representation. You should find the following sum modulo 10 Power 9 + 7:

314159
(a xor (b shl i))
i=0
where operation cor means exclusive OR operation, operation shl means binary shift to the left.
Please note, that we consider ideal model of binary integers. That is there is infinite number of bits in each number, and there are no disappearings (or cyclic shifts) of bits.
Input Format
The first line contains number a (1 < a < 2105) ) in binary representation. The second line contains number b (1 ≤ b < 2109) in the same format. All the numbers do not contain leading zeros.
Output Format
Output a single integer the required sum modulo 10 power 9 +7

Sample Input

10
1010

Sample Output

489429555

Table of Contents

Xor and Sum C Solution

#include <stdio.h>
#include <stdlib.h> 
#define MOD 1000000007
#define s(k) scanf("%d",&k);
#define sll(k) scanf("%lld",&k);
#define p(k) printf("%d\n",k);
#define pll(k) printf("%lld\n",k);
#define f(i,N) for(i=0;i<N;i++)
#define f1(i,N) for(i=0;i<=N;i++)
#define f2(i,N) for(i=1;i<=N;i++)
#define lim 314160
typedef long long ll;
void rev(char* in){
    int start=0,end=strlen(in)-1,i,l=strlen(in);
    char t;
    while(start<end){
        t=in[start];
        in[start]=in[end];
        in[end]=t;
        start++;
        end--;
    }
    for(i=strlen(in);i<lim+l;i++)
        in[i]='0';
}
int main(){
    char A[414160],B[414160];
    int i,num,len;
    ll X,sum,pos;
    scanf("%s",A);
    scanf("%s",B);
    len=strlen(B);
    rev(A);
    rev(B);
    num=0;
    pos=1;
    sum=0;
    for(i=0;i<lim-1;i++){
        if(B[i]=='1')
            num++;
        X=num;
        if(A[i]=='1')
            X=lim-X;
        sum=(sum+X*pos)%MOD;
        pos=(pos<<1)%MOD;
    }
    for(i=0;i<len;i++){
        X=num;
        sum=(sum+X*pos)%MOD;
        pos=(pos<<1)%MOD;
        if(B[i]=='1')
            num--;
    }
    
    pll(sum);
/*    printf("%s\n",A);
    printf("%s\n",B);*/
    return 0;
    
}

Xor and Sum C++ Solution

#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

// 10 ^     1010 =      1000 (8)
// 10 ^    10100 =     10110 (22)
// 10 ^   101000 =    101010 (42)
// 10 ^  1010000 =   1010010 (82)
// 10 ^ 10100000 =  10100010 (162)
//                 100111100 (316)

#define MOD(x) ((x) % 1000000007)

int64_t modpow(int64_t base, int64_t exp, int64_t modulus) {
    base %= modulus;
    int64_t result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}

int main() {
    vector<bool> a(500000, false);
    vector<bool> b(500000, false);
    string as, bs;
    cin >> as >> bs;
    for (int i = 0; i < as.size(); ++i) {
        a[i] = as[as.size() - 1 - i] == '1';
    }
    for (int i = 0; i < bs.size(); ++i) {
        b[i] = bs[bs.size() - 1 - i] == '1';
    }
    int64_t result = 0;
    int bset = 0;
    int carry = 0;
    const int n = 314160;
    for (int i = 0; bset || i < bs.size() || carry; ++i) {
        bset += b[i];
        if (i >= n) {
            bset -= b[i - n];
        }
        auto set = bset;
        auto unset = n - set;
        if (a[i]) {
            swap(set, unset);
        }
        auto bit = (carry + set) % 2;
        carry = (carry + set) >> 1;
        if (bit) {
            result = MOD(result + modpow(2, i, 1000000007));
        }
    }
    cout << result << endl;
    return 0;
}

Xor and Sum C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'xorAndSum' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. STRING a
     *  2. STRING b
     */

    public static int xorAndSum(string a, string b)
    {
        var result = 0L;
        var n = 314159;
        var m = 1000000007L;
        var exp = 1L;
        var num1sLsbToMsb = new int[b.Length + 1];
        var num1sMsbToLsb = new int[b.Length + 1];
        
        for (var i = 0; i < b.Length; ++i) {
            num1sLsbToMsb[i + 1] = num1sLsbToMsb[i] + (b[b.Length - 1 - i] - '0');
            num1sMsbToLsb[i + 1] = num1sMsbToLsb[i] + (b[i] - '0');
        }
        
        for (var i = 0; i < b.Length + n; ++i) {
            var num1s = 0;
            
            if (i < b.Length) {
                num1s = num1sLsbToMsb[i + 1];
            } else if (i >= n) {
                num1s = num1sMsbToLsb[(b.Length + n) - i];
            } else {
                num1s = num1sLsbToMsb[b.Length];
            }
            
            var num0s = (n + 1) - num1s;
            var ai = i < a.Length ? a[a.Length - 1 - i] - '0' : 0;
            
            result = (result + (((ai == 0 ? num1s : num0s) * exp) % m)) % m;
            exp = (exp * 2) % m;
        }
        
        return (int)result;
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string a = Console.ReadLine();

        string b = Console.ReadLine();

        int result = Result.xorAndSum(a, b);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Xor and Sum Java Solution

import java.util.*;



public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a, b;
        long sum, mod;
        long max = 314159;
        mod = 1000000007;

        a = in.next();
        b = in.next();

        int nA[] = new int[a.length()];
        int nB[] = new int[b.length()];
        setInverse(nA, a);
        setInverse(nB, b);

        sum = 0;

        long pow = 1;

        long count = 0;
        int len = Math.max(nA.length, nB.length);
        for (int i = 0; i < max; i++) {
            if (i < nB.length)
                count += nB[i];
            long multiplier = (i < nA.length && nA[i] == 1) ? max - count + 1 : count;
            sum = (sum + pow * multiplier) % mod;
            pow = (pow << 1) % mod;
        }
        
        for(int i = 0; i < nB.length; ++i){
            sum = (sum + pow*count) % mod;
            pow = (pow << 1L) % mod;
            count -= nB[i];
        }
        
        System.out.println(sum);
        
        in.close();
    }

    private static void setInverse(int[] nA, String a) {
        StringBuffer sb = new StringBuffer(a);
        sb.reverse();
        for (int i = 0; i < a.length(); i++) {
            nA[i] = sb.charAt(i) - '0';
        }
    }
}

Xor and Sum JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'xorAndSum' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. STRING a
 *  2. STRING b
 */

function xorAndSum(a, b) {
    [a,b] = [a,b].map(x=>BigInt("0b"+x));
    let s=a^b;
    for (let i=1n;i<=314159n;i++) s+=a^(b<<i);
    return s%1000000007n;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const a = readLine();

    const b = readLine();

    const result = xorAndSum(a, b);

    ws.write(result + '\n');

    ws.end();
}

Xor and Sum Python Solution

a = int('0b' + input(), 2)
b = int('0b' + input(), 2)
s = 0

for i in range(314160):
    s += (a ^ b << i)
print(s % (pow(10,9) + 7))