Impostor_Syndrome's blog

How to store this info in a bitmask?
By Impostor_Syndrome, history, 3 years ago, In English

I'm solving a problem in which I need to store the frequency of each digit from 0 to 9 in a bitmask.
Is it possible to do this?
If yes, then how?

  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

ignore

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

    But it only stores the parity of frequency. It doesn't store numerical frequency. Actually the question is a digit dp question in which I have to count all numbers in a range which have Freq of each digit as K, where K is given. So I was thinking how to make a dp state store the frequency.

    → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Bitmask stores 0/1 values so it would work only to check if the frequency is 0 or more.

You can represent every frequency as a binary number, e.g. 5 = 101, and write them one by one. It will be annoying. In particular, you need to figure out what's the length of every number. If each frequency is up to 100, you need 7 bits per number because $$$100 \leq 2^7$$$. The bitmask needs a length $$$70$$$ then.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If highest frequency is F Then you can represent the number in a number system base F So, dp will look like dp[F][F][F][F][F][F][F][F][F][F]. You can compress it in dp[F^10]

→ Reply