### D_Coder_03's blog

By D_Coder_03, history, 7 weeks ago,

PROBLEM STATEMENT :

You have given 4 numbers A, B, C, D and you have to perform an algorithm:-

int sum=0;

for(int i=A;i<=B;i++) {

for(int j=C;j<=D;j++)
sum+=i^j;

}

As the sum could be very large, compute it modulo 1000000007 (10e9+7).

Constraints : 1<=A,B,C,D<=1000000000

Time Limit — 1 sec

INPUT :- 4 integers A,B,C,D is given.

OUTPUT :- Print the sum after performing the algorithm.

EXAMPLE INPUT:- 1 2 3 4

EXAMPLE OUTPUT:- 14

EXPLANATION :- 1^3+1^4+2^3+2^4

2 + 5 + 1 + 6 = 14

This problem was asked in my recent coding round of Uber. Can anyone help me with its approach?

• +19

 » 7 weeks ago, # |   +26 It should be sufficient to just count contribution of each bit into the answer separately.
•  » » 7 weeks ago, # ^ |   0 But we cannot traverse from A to B or from C to D, then how will we count then contribution of each bit?...could you elaborate your answer more?
•  » » » 7 weeks ago, # ^ |   +8 for example i has 1 at certain places(let say it has 1 at position x) so when you will exor it with j you will add 2^x if j has 0 at that place or 0 otherwise. Therefore for every bit from 0 to 63rd bit you have to 2^x*(count(numbers with 1 at x in a to b)*count(numbers with 0 at x in c to d)+count(numbers with 0 at x in a to b )*count(numbers with 1 at x in c to d))
•  » » » » 7 weeks ago, # ^ |   +6 Understood!!
•  » » » » » 7 weeks ago, # ^ |   +3 a similar question came in july lunchtime/cook-off .u may see it's editorial for better visualization.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 If u did understood , can u explain me pls, I agree we'll have to find the number of set bits at some position x from 'a' to 'b' and number of unset bits from 'c' to 'd' and same vice versa ... But even in that we would have to iterate over entire range from a to b and from c to d , which would still in worst case take O(n) time and that won't work here.Pls if possible explain me , I know I am wrong somewhere
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +6 Hi Everyone, please I want a verification for my method or point out if I am wrong. let $A_1,A_2...A_k$ are the numbers in range $[A,B]$ and similarly let $C_1,C_2...C_m$ are the numbers in range $[C,D]$ so basically I have to calculate $\displaystyle \sum\limits_{i = 1}^k\displaystyle \sum\limits_{j = 1}^m A_i \,xor\,C_j$. but we know that $A_i \,xor\,C_j=(A_i +C_j)-2(A_i\,and\,C_j)$ also we know that $A\,and\,B+A\,and\,B=A\,and\,(B+C)$. Now let $\displaystyle \sum\limits_{j = 1}^mC_j=S_1$. So our inner summation $\displaystyle \sum\limits_{j = 1}^m A_i \,xor\,C_j$ becomes $mA_i+S_1-2(A_i\,and\,S_1)$. Now let $\displaystyle \sum\limits_{i= 1}^kA_i=S_2$. So $\displaystyle \sum\limits_{i = 1}^k (mA_i+S_1-2(A_i\,and\,S_1))$ is our final answer and it equals $m*S_2+k*S_1-2*(S_1\,and\,S_2).$ Since we can find $S_1,S_2$ in constant time so time complexity is $O(1).$ Please point out anyone if I am wrong.
•  » » » 7 weeks ago, # ^ |   +3 aah,bitwise and is not commutative over addition
•  » » » » 7 weeks ago, # ^ |   +3 i meant distributive**
 » 7 weeks ago, # |   0 Geometric progression sum with binary exponentiation
•  » » 7 weeks ago, # ^ |   +7 Not understanding the approach to it, can you explain your approach more clearly?
•  » » 7 weeks ago, # ^ |   0 Hey, I think you misunderstood the question (and I also). i^j is i xor j not i raised to j.
•  » » » 7 weeks ago, # ^ |   +1 Well it was mentioned there that '^' means xor...I forgot to mention that in the blog
 » 7 weeks ago, # |   +8 just off topic: It was on-campus or off-campus?
•  » » 7 weeks ago, # ^ |   +9 It was DTU on campus
•  » » » 7 weeks ago, # ^ |   0 Hey have placement tests started at DTU? or are these internship tests?
•  » » » » 7 weeks ago, # ^ |   0 I am not studying there, but yes acc to my knowledge both are going!
 » 7 weeks ago, # |   +16 Just count number of set bits for each position(bit) in A to B and same for C to D. Then ans is just contribution of each bit ie. For each bit contribution is ((no. of set bits in A-B)*(no. of unset C-D)+(no. of set bits in C-D)*(no. of unset A-B))*(2^position). Hope this helps.
•  » » 7 weeks ago, # ^ |   -13 fucking genius!!!!
•  » » 7 weeks ago, # ^ |   0 But bro we cannot traverse even from A to B or from C to D so how will we count the set and unset bits?
•  » » » 7 weeks ago, # ^ |   +20 Hint : For the ith bit, there's a pattern and pattern length is 2^(i+1).
•  » » » » 7 weeks ago, # ^ |   +1 Ohh...okay okay..understood how the concept will work..Thanks!
•  » » » » 7 weeks ago, # ^ |   0 Hint : For the ith bit, there's a pattern and pattern length is 2^(i+1). Can you elaborate the hint?
•  » » » 7 weeks ago, # ^ |   -6 Use Digit Dp
 » 7 weeks ago, # |   +11 pastebin link code if u want, (not thoroughly tested).
•  » » 7 weeks ago, # ^ |   0 Did you calculated each bit contribution for A to B and C to D with this code?
•  » » » 7 weeks ago, # ^ |   +3 I calculated until R at ith position bit, Observation :: 1] at ith position zeros are 2^i — 1, we remove that from R 2] Now there alternating pattern of 1 and 0 with each length of 2^(i+1) , you can calculate that by quotient and remainder dividing by 2^(i+1)
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Can you please explain why did you subtract 2^i-1 ?If we start from 0, then we can say that the pattern at ith position is (0000..2^i times) and then (1111....2^i times).We calculate number of zeros in [L,R] is = zeros[0,R] — zeros[0,L] . Number of ones is (R-L+1)-(no of zeros).
•  » » » » » 7 weeks ago, # ^ |   0 Why do we need to substract 2^i-1 from R ?
 » 7 weeks ago, # |   +53 wow i didnt know that taxi drivers should be good at cp nowadays, what a great time we live in!
•  » » 7 weeks ago, # ^ |   0 lol
•  » » 7 weeks ago, # ^ |   -15 What if Uber's algorithm fails some day and they have to find shortest path ;)
 » 7 weeks ago, # |   +6 This problem ultimately reduces to "Find number of setbits of ith bit for numbers between range x to y"To find this there is a pattern, run this prog you will understand https://ideone.com/vMaCNs
•  » » 7 weeks ago, # ^ |   0 Yes..I understood it after several explanations in the comments, thank you so much!
 » 7 weeks ago, # |   +1 its damn easy.i did a similar problem.just store the number of ones and zeros in both ranges.then just iterate over the 42 bits and pick zero from one set(a-b)and one from another and vice-versa.then multiply with 2^i(0-based index)using fast expo and sum it.and you get your answer
 » 7 weeks ago, # |   +4 Coding round for interships or coding round for full-time ?? @D_Coder_03
•  » » 7 weeks ago, # ^ |   +5 Mine was for Internship
•  » » » 7 weeks ago, # ^ |   +2 Could you share rest questions also in brief It will be helpful
•  » » » » 7 weeks ago, # ^ | ← Rev. 4 →   +8 There were 3 problems 1st problemCheck whether the string is good. A string is good if all its odd length substring are palindromes.Constraints 1<=|s|<=40ExampleINPUT- aaaaa OUTPUT- YESINPUT- xyz OUTPUT- NO2nd problemA number N is given. Find out the minimum cost to make it a good number.A good number is the sum of two numbers which are positive power of a single digit odd prime number.In one operation: You can add 1 to n with x cost You can subtract 1 from n with y cost You can do the operations any number of times.Contraints: 1<=N,x,y<=1e9Example INPUT- 4 5 6 OUTPUT- 24 Explanation- good no. is 3^1+5^1=8->(8-4)*6 = 243rd problem was in the blog itselfHOPE IT HELPS
•  » » » » » 7 weeks ago, # ^ |   0 Thanks man
•  » » » » » » 7 weeks ago, # ^ |   0 In problem 2 , for the given input 4,5,6 don't you think that the output should be 0 as N=4 is already a good no. coz it can be represented as 1^1+3^1.
•  » » » » » » » 7 weeks ago, # ^ |   0 I forgot to add prime there..edited it though.
•  » » » » » 7 weeks ago, # ^ |   +1 Just a try at this..Will this logic work? Bruteforce for all powers of 3 , 5 and 7 and just check which combination gives the smallest answer becoz we know that the number of elements in each of their power lists cannot be more than 64.?
•  » » » » » » 7 weeks ago, # ^ |   +1 An also how many questions were required to be solved for clearing this round ? 2 out of 3 ?
•  » » » » » » » 7 weeks ago, # ^ |   +1 I guess all 3 will be required because first 2 were easy and the 3rd one was the only question which had extremely less fully accepted submissions.
•  » » » » » » » » 7 weeks ago, # ^ |   +4 I thought so XD. Too difficult to crack now it seems. Were there any partial points for the 3rd problem. XD
•  » » » » » » » » » 7 weeks ago, # ^ |   +4 Yes partial pts were available for every question
•  » » » » » » 7 weeks ago, # ^ |   +1 Just precompute the sums of all the powers of 3 5 and 7 taking 2 at a time less than or equal to 1e9 then check between which 2 nos the N lies.
•  » » » » » » » 7 weeks ago, # ^ |   +3 Yes this is also another bruteforce logic which can be used.
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 Hey,Can you help me with the second question Edit:Got it Thanks
•  » » » » » 7 weeks ago, # ^ |   0 In the second question, Is both prime numbers can be equal? Ex- 6 4 5the answer is zero because 3^1+3^1 = 6.
•  » » » » » » 7 weeks ago, # ^ |   +3 No, the nos are different
•  » » » » » 7 weeks ago, # ^ |   0 just curious. In q1. can we just find if whole string contain 1 char only or it is alternate with 2 char. Is this the logic??
•  » » » » » » 7 weeks ago, # ^ |   +3 If the string contains the condition a[i]!=a[i+2] then the ans is false otherwise true
 » 7 weeks ago, # | ← Rev. 3 →   0 As the constraints are enormous we have to do something with bits First thought after this is to calculate every possible pair. If we can find the total no.s between A and B with 1 at a particular place we can solve the question Now we have no idea how to do that so we can take some examples So first 15 digits are 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111  Now we will find total no.s from 1 to 15 with ith bit zero there are (1<
 » 7 weeks ago, # | ← Rev. 2 →   +3 Hi Everyone, please I want a verification for my method or point out if I am wrong. let $A_1,A_2...A_k$ are the numbers in range $[A,B]$ and similarly let $C_1,C_2...C_m$ are the numbers in range $[C,D]$ so basically I have to calculate $\displaystyle \sum\limits_{i = 1}^k\displaystyle \sum\limits_{j = 1}^m A_i \,xor\,C_j$. but we know that $A_i \,xor\,C_j=(A_i +C_j)-2(A_i\,and\,C_j)$ also we know that $A\,and\,B+A\,and\,B=A\,and\,(B+C)$. Now let $\displaystyle \sum\limits_{j = 1}^mC_j=S_1$. So our inner summation $\displaystyle \sum\limits_{j = 1}^m A_i \,xor\,C_j$ becomes $mA_i+S_1-2(A_i\,and\,S_1)$. Now let $\displaystyle \sum\limits_{i= 1}^kA_i=S_2$. So $\displaystyle \sum\limits_{i = 1}^k (mA_i+S_1-2(A_i\,and\,S_1))$ is our final answer and it equals $m*S_2+k*S_1-2*(S_1\,and\,S_2).$ Since we can find $S_1,S_2$ in constant time so time complexity is $O(1).$ Please point out anyone if I am wrong.
•  » » 7 weeks ago, # ^ |   +3 okay:a ^ b = a + b — 2 * (a & b) [it's true]you are writing: A and B + A and B = A and (B + C) [it is not true]maybe you meant it?A and B + A and C = A and (B + C)however for A = B = C = 1=> A and B + A and C = 1 + 1 = 2, A and (B + C) = 1 and 2 = 01 and 10 = 0, 2 != 0similar properties are very beautiful, if you wanted to write something like that, please share. That's very beautiful
•  » » » 7 weeks ago, # ^ |   +3 I am so sorry. Thanks for pointing. This mistake (A and B + A and C = A and (B + C)) came because of Electrical stuff because there only LEDs are either on/off(0/1 bit) and for this that expression is true. But here we have Integers. Sorry, my method is useless then.
 » 7 weeks ago, # | ← Rev. 5 →   0 Sorry,I didn't see the operator.Its exor I thought its addition. Pls don't read Try using prefix sum.Time complexity=O(n). Create a array of length=max_sum you can achieve+1 say the name of array is arr Initialize it with zeros Then run a loop from A to B: arr[i+C]+=1 arr[i+D+1]-=1 Then run a loop on array and perform arr[i]+=arr[i-1] Create a new var ans=0 now again iterate arr: and do ans+=arr[i]*i
•  » » 6 weeks ago, # ^ |   +3 Well O(n) will give TLE bro...constraints are upto 10^9.