Блог пользователя prathams

Count numbers of 1 multiple of 3 till N
Автор prathams, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Test this code...

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what does "ex" variable refer to?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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...

      → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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((

      → Ответить