nkb-xyz's blog

a xor b = y how to count the pairs {a,b} effieciently
By nkb-xyz, history, 119 minutes ago, In English

How to efficiently count the number of pairs having a xor b equal to m where 1<=a<=n , 1<=b<=n and n varies 2 to 2e5 and m also varies 1 to n

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
118 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nkb-xyz (previous revision, new revision, compare).

→ Reply
»
108 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint: If a and m are fixed, can you find a value of b, such that a ^ b = m?

→ Reply
  • »
    »
    104 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    yeah b = m^a and complexity will be o(n) right?? got it ... it this final like cant we go beyond that like logarithmic or like lesser than this

    → Reply
    • »
      »
      »
      80 minutes ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      My bad, you still need to check if the corresponding b is <= n, so n — 1 is not correct, in general it is less than that. So I failed in my attempt to make it better than O(n)

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

        i think its not possible... i gave up on my approach

        → Reply
    • »
      »
      »
      48 minutes ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Good job! How many possible values of a are there?

      (Don't overthink the complexity — what you are shooting for is O(n) )

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

        For linear time we can just iterate a from 1 to n and check if the corresponding b is in 1 to n or nah. I think OP is asking for a sublinear algorithm.

        → Reply