| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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.
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.
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?
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.
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.
How many integers 'z' are there such that z <= 101000100? That answer should be fairly trivial.
Now let's say y > x
Note that nothing has really changed. After compression
but you clearly can't use the first two bits or otherwise z would be greater than x.
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.
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))
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.
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.
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.
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.
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