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.
I will just explain my algorithm below using the example a='1011'=11 and b='11'=3 with n=5
the problem ask us to compute
'1011'xor'11' =(1000) = bx2^0+a+err1
+'1011'xor'110' =(1101) = bx2^1+a+err2
+'1011'xor'1100' =(111) = bx2^2+a+err3
+'1011'xor'11000' =(10011) = bx2^3+a+err4
+'1011'xor'110000' =(111011) = bx2^4+a (no err from here)
+'1011'xor'1100000' =(1101011) = bx2^5+a
with err1=4+2, err2=4, err3=16, err4=16 with total error=sum=42.
so we can reduce the problem into two parts
1) compute the trivial sum bx(2^0+2^1+...+2^n)+ax(n+1) %1e9+7
2) compute the error terms
here i will explain how to compute the total errors by this example, the detailed algorithm can be found below
these errors come from when shifting b to the left, each '1' in b will only hit the digits '1' of a on the left.
for example,
'1 1 ' will hit ' 1 0 11 '
leading to an error 2x(1+2+8)=2+4+16 (times 2 here since both of those 1 become 0 after we take xor)
also ' 1 1' will only hit ' 1 0 1 1'
leading to an error 2x(2+8)=4+16
you can see that 2,4,16,4,16 are exactly the terms in err1--err4.
fromcollectionsimportdefaultdictM=1000000007a=str(input())b=str(input())# need to change n into 314159n=314159# pre-compute powers of 2 up to n=314159pof2=[1]foriinrange(n+1):pof2.append((pof2[-1]*2)%M)# use a default list to count the number of 1's in b in the right k digitslen_a=len(a)len_b=len(b)#print(len_a,len_b)cnt_b=defaultdict(int)cnt_b[0]=int(b[-1])foriinrange(1,len_b):cnt_b[i]=cnt_b[i-1]+int(b[-i-1])# extend to the length of aforiinrange(len_b,len_a):cnt_b[i]=cnt_b[len_b-1]# using pof2 to compute num_a%M,num_b%Mnum_a=0num_b=0foriinrange(len_a):ifint(a[-1-i])!=0:num_a+=pof2[i]foriinrange(len_b):ifint(b[-1-i])!=0:num_b+=pof2[i]#print(num_a,num_b)#compute the offsetoffset=0foriinrange(len_a):ifint(a[-i-1])!=0:offset+=pof2[i+1]*cnt_b[i]#print(offset)# n=314159, which is very largeanswer=(num_b*(pof2[n+1]-1)+num_a*(n+1)-offset)%Mprint(answer)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Xor and Sum
You are viewing a single comment's thread. Return to all comments →
A python solution
I will just explain my algorithm below using the example a='1011'=11 and b='11'=3 with n=5
the problem ask us to compute
'1011'xor'11' =(1000) = bx2^0+a+err1
+'1011'xor'110' =(1101) = bx2^1+a+err2
+'1011'xor'1100' =(111) = bx2^2+a+err3
+'1011'xor'11000' =(10011) = bx2^3+a+err4
+'1011'xor'110000' =(111011) = bx2^4+a (no err from here)
+'1011'xor'1100000' =(1101011) = bx2^5+a
with err1=4+2, err2=4, err3=16, err4=16 with total error=sum=42.
so we can reduce the problem into two parts
1) compute the trivial sum bx(2^0+2^1+...+2^n)+ax(n+1) %1e9+7
2) compute the error terms
here i will explain how to compute the total errors by this example, the detailed algorithm can be found below
these errors come from when shifting b to the left, each '1' in b will only hit the digits '1' of a on the left.
for example,
'1 1 ' will hit ' 1 0 11 '
leading to an error 2x(1+2+8)=2+4+16 (times 2 here since both of those 1 become 0 after we take xor)
also ' 1 1' will only hit ' 1 0 1 1'
leading to an error 2x(2+8)=4+16
you can see that 2,4,16,4,16 are exactly the terms in err1--err4.