• API
• FAQ
• Tools
• Archive
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.

Top