### john_hopes's blog

By john_hopes, history, 4 years ago, ,

In a bitmask DP problem, there 10 digits. And for every digits I need to store three types of data ( Not used, Used and Using ). One way to solve this is using two bitmask. But for some other reasons It is not possible to use two bitmask in my case. Is there any other memory efficient way to do so? Is there any good resources for learning this?

• 0

 » 4 years ago, # |   0 Auto comment: topic has been updated by john_hopes (previous revision, new revision, compare).
 » 4 years ago, # |   0 Could you link the problem? It would make it easier to understand the constraints, specifics, etc.
 » 4 years ago, # | ← Rev. 7 →   0 Use map or hashtable. Also you can use numeral system with base 3. Get: digit[i] = (x / 3^i)) % 3. Set: x = x + (value - (x / 3^i)) % 3) * 3^i 3^10 == 59049, so value of your mask will be in [0..59048]. Instead of slow division operation you can precompute modInverse(3^i, 2^32) and multiply. x / (3^i) == x * modInverse(3^i, 2^32) In unsigned 32-bit integer type.