CODEWITHSUNDEEP
c++algorithmbitwise-operatorsbitmask
glam videos opera
glam videos opera

Reputation: 3

Finding submask of a mask within a given range

How to find the largest sub mask of a given mask which is just equal or lesser than a given value r. For example the sub masks of a mask(5 in binary 101) is 4(100 in binary),1(001 in binary). Now if given r=5,then answer would be 5,if r =3,then answer would be 1 etc.. I want an efficient algorithm which can calculate it in less time.

But this code giving me time limit exceeded .as the value of mask can be <=10^9 It will be very helpful if anyone give me optimized approach to reduce the time complexity.

what I was trying:

for(int i=mask;i>0;i=(i-1)&mask) if(i<=r) print(i);

Upvotes: 0

Views: 851

Answers (1)

lenik
lenik

Reputation: 23498

This seems to work quite fast (no more than 32 iterations for 10^9 numbers, basically O(logN) complexity):

>>> def submask( mask, r ) :
...     result = 0
...     for bit in range(32,-1,-1) :
...         value = 1 << bit
...         if value & mask == 0 : continue
...         if value | result <= r :
...             result |= value
...     return result
... 
>>> submask(5,1)
1
>>> submask(5,3)
1
>>> submask(5,4)
4
>>> submask(5,5)
5
>>> submask(7,2)
2
>>>

Upvotes: 2

Related Questions