kn0ppers's blog

By kn0ppers, history, 5 years ago, In English

Hi all,

recently i attended a job interview where i got the following question:

Given x and y, find the number of integers such that for z in [1..x] z & y > 0?

Is there a faster way to compute this other than iterating through all the ints from [1..x]? Is there some sort of trick to compute this directly? I appreciate anyone taking the time to give me hints/tricks to compute this.

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

| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Let's compute the number of values of z & y with the most significant bit being x. We're definitely going to have a 1 in z, and also we can't have any positions greater than x where both z and y have a 1 in that position. So we can just do 2 ^ (positions that are 0 and greater than x) and also the ones lower can be anything, and also you need to make sure z doesn't go above x.

I haven't thought about it that much but something like this seems like it would work.

  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Thank you for your reply.

    I actually thought of a similar approach but i got stuck on how to count the numbers from [1<<u, x] (u being x's MSB) without going through all the numbers in this interval. Should one just keep the MSB on and keep turning bits on and off while making sure not to go over x or are there some tricks here?

    • »
      »
      »
      5 years ago, hide # ^ |
      ← Rev. 4  
      Vote: I like it 0 Vote: I do not like it

      I don't think you need digit DP or anything complicated like that. Let's find, instead, the numbers such that z & y = 0 and work through an example where x > y.

      x  10011000010100
      y  01001101010000
      ----------------
      z  x0xx00x0x0xxxx
      

      Note that z must be of the form specified in order to have z & y = 0. Now strip those 0 bits away (and the associated bits in x and y) because you know you can't set them to 1.

      x  101000100
      y  000000000
      ----------------
      z  xxxxxxxxx
      

      How many integers 'z' are there such that z <= 101000100? That answer should be fairly trivial.

      Now let's say y > x

      x  00011000010100
      y  01001101010000
      ----------------
      z  x0xx00x0x0xxxx
      

      Note that nothing has really changed. After compression

      x  001000100
      y  000000000
      ----------------
      z  xxxxxxxxx
      

      but you clearly can't use the first two bits or otherwise z would be greater than x.

»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I think this can be done via digit dp.

If anyone is able to find a link for a similar problem where I can test my code it would be highly appreciated.

»
5 years ago, hide # |
← Rev. 3  
Vote: I like it +6 Vote: I do not like it

Quick sketch:

Let solve(x,y) be the answer to our problem. Let X be the current MSB of x (0-indexed) and Y be the corresponding bit in y. If Y==1, then our answer is 2^X-2^b+(x%(1<<X))+1, where b is the # unset bits in y after position X.

Else, we can utilize recursion -> answer is 2^X-2^b+solve(x%(1<<X),y%(1<<X)) (Aka, chop off the MSB).

Runtime: O(log(x))

  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Thank you for your reply.

    Interesting approach! I tried implementing this right now, i think maybe the recursion here contains a mistake, or i misunderstood your solution. Consider the following example:

    x = 128 = 10000000 (base 2)

    y = 64 = 1000000 (base 2)

    * MSB(x) = 7 (0 indexed)

    * y & (1<<7) = 0 => 2^7 - 2^0 + solve(128,64)

    This would yield 127 whereas the solution should be all numbers between [64,128] i.e. 64.

    • »
      »
      »
      5 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +1 Vote: I do not like it

      Yeah there may have been a minor bug in my sketch, but it should be able to lead you to the solution.

      For your example, though, it should lead to 2^7-2^6+solve(0,0)=64.

      • »
        »
        »
        »
        5 years ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        Alright, thanks again man.

        Will build on it once i sober up.

        P.S.: I upvoted all comments here but for some reason someone downvoted them all.

»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Probably not helpful, but iterate through all submasks of y and find all that are within 1..x. If you can find a way to binary search it, it might be log time.

»
5 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

We can iterate through all the bits of y and then check if ith bit of y is set then we can count the number of z's in [1... x] having ith bit as set. This can be done using :- Link