prathams's blog

Count numbers of 1 multiple of 3 till N
By prathams, history, 9 years ago, In English

How to count numbers whose binary representation has number of 1's multiple of 3 for all numbers between 1 to N.

For ex — N = 19 then ans = 5 Since, 7, 11, 13, 14, 19 have number of 1's multiple of 3.

Constraint : n < 1016

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

Comments Comments (11)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Test this code...

If it was correct and you have any question you can ask...

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

    what does "ex" variable refer to?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The algorithm is this:

      First if the N has 3 '1' digits we ++ the ANS

      then we consider the first '1' digit of the number N (from left) as '0' so we can change other digits any way we want so C(number of other digits,3) will be add to ANS...

      then we will change the leftest digit to '1' and find next '1' digit from left and consider it as '0' and add C(number of other digits,2) to ANS...

      and also this for the next '1'...

      Maybe it can be coded more clean...

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

    This code is not giving correct result as for n = 64, answer should be 21 but its showing 18.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      are you sure the answer should be 21???

      I think it should be C(6,3)=20...

      New code(just an 'IF' added)

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

        FYI, for n = 64, answer = 21 since 7 11 13 14 19 21 22 25 26 28 35 37 38 41 42 44 49 50 52 56 63 these all numbers have multiple of 3 one's.

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

          Oh sry multiple of 3...

          I solved it for just 3...

          sry... :/

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +23 Vote: I do not like it

            wrong account bro.you sent from fake one.

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

It can be solved using dp

dp[i][j][k] — number of numbers with i bits(possible with zeroes in front), j shows if we used in some 1 bit of n 0 in our number, k — number of 1 bits modulo 3

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

    Thanks vintage_Vlad_Makeev, can you please give some more details on it ?

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

      Let's understand how are numbers <=n arranged.

      At first they have some prefix of n. Then there is a position i that n[i]>x[i] and then can be anything.

      For example

      10010101 10001110

      100 — is common prefix of this numbers. Then in n we have 1 and in our number we have 0. And after this position we can do anything as this number will be less or equal than n.

      So we can do a dp with states (number of bits left,number of 1 bits modulo 3, is there a position i n[i]>x[i]). So there will be only 64*3*2 states.

      My Englist is terrible, sorry((

      → Reply