D_Coder_03's blog

By D_Coder_03, history, 14 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

It should be sufficient to just count contribution of each bit into the answer separately.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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))

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Understood!!

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          a similar question came in july lunchtime/cook-off .

          u may see it's editorial for better visualization.

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          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

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Geometric progression sum with binary exponentiation

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Not understanding the approach to it, can you explain your approach more clearly?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, I think you misunderstood the question (and I also). i^j is i xor j not i raised to j.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Well it was mentioned there that '^' means xor...I forgot to mention that in the blog

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

just off topic: It was on-campus or off-campus?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    It was DTU on campus

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey have placement tests started at DTU? or are these internship tests?

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not studying there, but yes acc to my knowledge both are going!

»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    fucking genius!!!!

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Hint : For the ith bit, there's a pattern and pattern length is 2^(i+1).

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Ohh...okay okay..understood how the concept will work..Thanks!

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hint : For the ith bit, there's a pattern and pattern length is 2^(i+1). Can you elaborate the hint?

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hi can you explain about the pattern? I cannot understand ur statement.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          For every ith bit there is a pattern of they change....for ex- 0-7

          0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,

          0th bit repeats pattern at 2 , 1st bit at 4 , 2nd bit at 8 and so on...

          Hope you understand!

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks. Do u have a working code? If u have share the code please.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Use Digit Dp

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

pastebin link code if u want, (not thoroughly tested).

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you calculated each bit contribution for A to B and C to D with this code?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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)

      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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).

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why do we need to substract 2^i-1 from R ?

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think I understand why we subtract 2^i — 1 from R. You will get it too. Just start writing numbers in binary form but start from 1 instead from 0. The code link also calculates set bit in ith position for the numbers 1 to R and not 0 to R. This should help.

»
14 months ago, # |
  Vote: I like it +53 Vote: I do not like it

wow i didnt know that taxi drivers should be good at cp nowadays, what a great time we live in!

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes..I understood it after several explanations in the comments, thank you so much!

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Coding round for interships or coding round for full-time ?? @D_Coder_03

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Mine was for Internship

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Could you share rest questions also in brief
      It will be helpful

      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 4   Vote: I like it +8 Vote: I do not like it

        There were 3 problems

        1st problem

        Check whether the string is good. A string is good if all its odd length substring are palindromes.

        Constraints 1<=|s|<=40

        Example

        INPUT- aaaaa OUTPUT- YES

        INPUT- xyz OUTPUT- NO

        2nd problem

        A 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:

        1. You can add 1 to n with x cost

        2. You can subtract 1 from n with y cost

        You can do the operations any number of times.

        Contraints: 1<=N,x,y<=1e9

        Example

        INPUT- 4 5 6 OUTPUT- 24 Explanation- good no. is 3^1+5^1=8->(8-4)*6 = 24

        3rd problem was in the blog itself

        HOPE IT HELPS

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks man

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I forgot to add prime there..edited it though.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.?

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            An also how many questions were required to be solved for clearing this round ? 2 out of 3 ?

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                14 months ago, # ^ |
                  Vote: I like it +4 Vote: I do not like it

                I thought so XD. Too difficult to crack now it seems. Were there any partial points for the 3rd problem. XD

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it +4 Vote: I do not like it

                  Yes partial pts were available for every question

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Yes this is also another bruteforce logic which can be used.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              Rev. 3   Vote: I like it +3 Vote: I do not like it

              how to precompute the sums of all the powers of 3,5,7 taking 2 at a time ? I mean like for example we choose 3 and 5, then we can store all combinations of 3^x . 5^y in sorted order or store in a set but how to do it ? just like a loop

              set<int> st;
              for(int x=0;pow(3,x)<1e9;x++)
                for(int y=0;pow(5,y)+pow(3,x)<1e9;y++)
                   st.insert(pow(3,x)+pow(5,y));
              

              please do we need to do something like this ?

              if you have code for it, please share.
              
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          Hey,Can you help me with the second question Edit:Got it Thanks

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In the second question, Is both prime numbers can be equal? Ex- 6 4 5

          the answer is zero because 3^1+3^1 = 6.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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??

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            If the string contains the condition a[i]!=a[i+2] then the ans is false otherwise true

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
  • 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<<i)-1 no of zeroes at ith place before the start of the pattern
  • Length of the pattern is (1<<(i+1)) for every place
  • so total zeroes after pattern starts is ((length of pattern) / 2) * total_no_of_complete_pattern + zeroes from a partial pattern that may of may not form at the end
  • total_no_of_complete_pattern (N)= (15 — ((1<<i) — 1) ) / ( 1<<i+1 ) now we can calculate the 1 part for 2 part we have a partial pattern of length (L) = ( 15 — ((1<<i) — 1) ) % ( 1<<i+1 ) now we can find no. of zeroes from it with simple if else
»
14 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 != 0

    similar properties are very beautiful, if you wanted to write something like that, please share. That's very beautiful

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
14 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Well O(n) will give TLE bro...constraints are upto 10^9.

»
3 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it
Code
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If there is any mistake feel free to correct me :)

»
2 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

For each integer in range, a to b and range c to d find the number of integers having i-th (0 <= i <= 30) bit set and unset.

Let c11 denoted the count of integers in range a to b having i-th bit set. Then c12 = (b-a+1-c11) integers are having bits unset in this range.

Similarly, let c21 denoted the count of integers in range c to d having i-th bit set. Then c22 = (d-c+1-c21) integers are having bits unset in this range.

Now for each i-th bit in range (0,30). Add to answer the value equals ((c11*c22 + c12*c21) % mod) *(1LL<<i)) % mod where mod = 1e9+7.

Pseudo code

Reference GFG article: Count integers up to N having K-th bit set in O(1)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    understood the solution ! Is there some derivation on how ((n>>(k+1))<<k) gives count of numbers in range [1 to n-1] having kth bit set

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's all about finding "how many times the pattern is repeating?". Pls, try to convince yourself by doing it with small numbers up to 50 or so.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Hello! Is there any way to check the code approach to this problem?

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is my approach for the problem:

Note considering the MOD part in the code (that can be included if required)

#include <bits/stdc++.h>
using namespace std;
#define int long long

// return the count of number of 1's at ith bit in a range [1, n]
long long getcount(long long n, int k)
{
	n++;
	long long res = (n >> (k + 1)) << k;
	if ((n >> k) & 1) res += n & ((1ll << k) - 1);
	return res;
}

signed main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int num1 = b - a + 1;
    int num2 = d - c + 1;
    int bit_count_outer[64], bit_count_inner[64];
    for(int i = 0; i <= 63; i++){
        bit_count_outer[i] = getcount(b, i) - getcount(a-1, i);
    }
    for(int i = 0; i <= 63; i++){
        bit_count_inner[i] = getcount(d, i) - getcount(c-1, i);
    }
    int sum = 0;
    int contrib = 1;
	for(int i = 0; i <= 63; i++){
	    int outer_one_count = bit_count_outer[i];
	    int outer_zero_count = num1 - outer_one_count;
	    int inner_one_count = bit_count_inner[i];
	    int inner_zero_count = num2 - inner_one_count;
	    int sum1 = (outer_one_count * inner_zero_count) + (outer_zero_count * inner_one_count);
	    sum +=  contrib * sum1;
	    contrib *= 2;
	}
	cout << "The sum is: " << sum << endl;
	return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is this what they ask to be a driver?