SHARE
TWEET

Untitled

a guest Oct 21st, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from itertools import chain
  2. import operator
  3. import random
  4.  
  5. def missing1(a, n, seq):
  6.   if n == 1:
  7.     return a
  8.   x = reduce(operator.xor, xrange(a, a + n))
  9.   x = reduce(operator.xor, seq, x)
  10.   return x
  11.  
  12.  
  13. def missing2(a, n, seq):
  14.   if n == 2:
  15.     return (a, a + 1)
  16.   x = reduce(operator.xor, xrange(a, a + n))
  17.   x = reduce(operator.xor, seq, x)
  18.  
  19.   h_bit = 1 << (x.bit_length() - 1)
  20.  
  21.   a1, a2 = 0, 0
  22.   for x in xrange(a, a + n):
  23.     if x & h_bit:
  24.       a1 ^= x
  25.     else:
  26.       a2 ^= x
  27.  
  28.   for x in seq:
  29.     if x & h_bit:
  30.       a1 ^= x
  31.     else:
  32.       a2 ^= x
  33.   if a1 > a2:
  34.     return (a2, a1)
  35.   return (a1, a2)
  36.  
  37.  
  38. def main():
  39.   for _ in xrange(1000):
  40.     n = random.randint(1, 50000)
  41.     a = random.randint(0, 2147483647 - n + 1)
  42.     pick = random.randint(a, a + n - 1)
  43.     ary = range(a, pick) + range(pick + 1, a + n)
  44.     random.shuffle(ary)
  45.     assert missing1(a, n, ary) == pick, (a, n, pick)
  46.  
  47.   for _ in xrange(1000):
  48.     n = random.randint(2, 50000)
  49.     a = random.randint(0, 2147483647 - n + 1)
  50.     pick1 = random.randint(a, a + n - 1)
  51.     pick2 = random.randint(a, a + n - 2)
  52.     if pick2 >= pick1:
  53.       pick2 += 1
  54.     else:
  55.       pick1, pick2 = pick2, pick1
  56.     ary = list(
  57.         chain(xrange(a, pick1),
  58.               xrange(pick1 + 1, pick2),
  59.               xrange(pick2 + 1, a + n)))
  60.     random.shuffle(ary)
  61.     assert missing2(a, n, ary) == (pick1, pick2), ((a, n), (pick1, pick2))
  62.  
  63. if __name__ == '__main__':
  64.   main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top