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

Don't know why this code is running
Автор silenttkillerr, история, 14 месяцев назад, По-английски

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/

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

»
14 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

Because value of k <= 100

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

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

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

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

      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
      → Ответить