silenttkillerr's blog

Don't know why this code is running
By silenttkillerr, history, 14 months ago, In English

I was solving a problem from Leetcode https://leetcode.com/problems/count-pairs-of-points-with-distance-k/

In this problem i am only checking from (i to i+100) and it passed , i not have any proof how pair will exist only till i+100,can anyone provide any proof or intuition.

code : https://leetcode.com/submissions/detail/1051363856/

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

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

considering x1<=x2 (x1^x2)>=(x2-x1) (x1^x2)<=k (x2-x1)<=k x2<=x1+k

in case x2 is greater than x1+k then (x1^x2)>k and hence (x1^x2)+(y1^y2)>k

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

Because value of k <= 100

My submission — https://leetcode.com/submissions/detail/1051139486/

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

    can you prove it, like we have (x,y) and (x+51,y+51) there xor will never exceed 100

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      xor of any two number is always greater than or equal to their absolute difference

      x - y == (x ^ y) - ((~x & y) << 1)

      x >= y 
(x^y)=x-y in case (x&y)==y 
example -> (6,4)
otherwise it will be always greater than (x-y) 

(x^(x+51))>=51
(y^(y+51))>=51
so there combined sum will be greater than or equal to 102
      → Reply