Why this code is showing 'Terminated due to timeout' on Hackerrank ?
I'm trying to do a task at Day 29: Bitwise AND in '30 days of code' on Hackerrank. Here is the task:
Task
Given set S = {1,2,3,...N}. Find two integers, A and B (where A < B), from set S such that the value of A & B is the maximum possible and also less than a given integer, K. In this case, & represents the bitwise AND operator.
Input Format
The first line contains an integer, T, the number of test cases. Each of the T subsequent lines defines a test case as 2 space-separated integers, N and K, respectively.
Constraints
1 <= T <= 10^3
2 <= N <= 10^3
2 <= K <= NOutput Format
For each test case, print the maximum possible value of A & B on a new line.
Sample Input
3
5 2
8 5
2 2
Sample Output
1
4
0
Explanation
N = 5, K = 2, S = {1,2,3,4,5}
All possible values of and are:
1. A = 1, B = 2; A & B = 0
2. A = 1, B = 3; A & B = 1
3. A = 1, B = 4; A & B = 0
4. A = 1, B = 5; A & B = 1
5. A = 2, B = 3; A & B = 2
6. A = 2, B = 4; A & B = 0
7. A = 2, B = 5; A & B = 0
8. A = 3, B = 4; A & B = 0
9. A = 3, B = 5; A & B = 1
10. A = 4, B = 5; A & B = 4The maximum possible value of A&B that is also < (K = 2) is 1, so we print 1 on a new line.
Here is my code:
import math
import os
import random
import re
import sys
if __name__ == '__main__':
t = int(sys.stdin.readline())
for t_itr in range(t):
nk = sys.stdin.readline().split()
n = int(nk[0])
k = int(nk[1])
lst1 = [(a, b) for a in range(1, n + 1) for b in range(a + 1, n + 1)]
lst2 = [ a & b for (a,b) in lst1 if a & b < k]
print(max(lst2))
This task has total 6 test cases, in test case 1 and 2, my code is True, but in 4 next test cases, it raise: 'Terminated due to timeout'.
Can you explain for me what am I wrong ? And what can I do to finish all the test cases? Thanks for helping me !
The max of (something) such that (something) is less than K should be K-1. Unless it's not possible for some reason.
So let's have a look:
for n in range(2, 256):
for k in range(2, n + 1):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
t = "*" if m == k - 1 else " "
print("{:s} {:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(t, n, k, m, n, k, m, n - k, k - m))
Sample output:
N K M N K M N-K K-M
----------------------------------------------
2 2 0 00000010 00000010 00000000 0 2
* 3 2 1 00000011 00000010 00000001 1 1
* 3 3 2 00000011 00000011 00000010 0 1
* 4 2 1 00000100 00000010 00000001 2 1
* 4 3 2 00000100 00000011 00000010 1 1
4 4 2 00000100 00000100 00000010 0 2
* 5 2 1 00000101 00000010 00000001 3 1
* 5 3 2 00000101 00000011 00000010 2 1
5 4 2 00000101 00000100 00000010 1 2
* 5 5 4 00000101 00000101 00000100 0 1
* 6 2 1 00000110 00000010 00000001 4 1
* 6 3 2 00000110 00000011 00000010 3 1
6 4 2 00000110 00000100 00000010 2 2
* 6 5 4 00000110 00000101 00000100 1 1
6 6 4 00000110 00000110 00000100 0 2
* 7 2 1 00000111 00000010 00000001 5 1
* 7 3 2 00000111 00000011 00000010 4 1
* 7 4 3 00000111 00000100 00000011 3 1
* 7 5 4 00000111 00000101 00000100 2 1
* 7 6 5 00000111 00000110 00000101 1 1
* 7 7 6 00000111 00000111 00000110 0 1
* 8 2 1 00001000 00000010 00000001 6 1
* 8 3 2 00001000 00000011 00000010 5 1
* 8 4 3 00001000 00000100 00000011 4 1
* 8 5 4 00001000 00000101 00000100 3 1
* 8 6 5 00001000 00000110 00000101 2 1
* 8 7 6 00001000 00000111 00000110 1 1
8 8 6 00001000 00001000 00000110 0 2
* 9 2 1 00001001 00000010 00000001 7 1
* 9 3 2 00001001 00000011 00000010 6 1
* 9 4 3 00001001 00000100 00000011 5 1
* 9 5 4 00001001 00000101 00000100 4 1
* 9 6 5 00001001 00000110 00000101 3 1
* 9 7 6 00001001 00000111 00000110 2 1
9 8 6 00001001 00001000 00000110 1 2
* 9 9 8 00001001 00001001 00001000 0 1
Apparently, the max is often K-1 (starred rows), so it may be easier to find out when it's not K-1. Also, the max seems to be either K-1 or K-2.
Another test, showing only when the max is not K-1. This time we sort by K first, then N.
for k in range(2, 256):
for n in range(k, 256):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
if m != k - 1:
print("{:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(n, k, m, n, k, m, n - k, k - m))
And a sample from the output follows.
N K M N K M N-K K-M
----------------------------------------------
2 2 0 00000010 00000010 00000000 0 2
----------------------------------------------
4 4 2 00000100 00000100 00000010 0 2
5 4 2 00000101 00000100 00000010 1 2
6 4 2 00000110 00000100 00000010 2 2
----------------------------------------------
6 6 4 00000110 00000110 00000100 0 2
----------------------------------------------
8 8 6 00001000 00001000 00000110 0 2
9 8 6 00001001 00001000 00000110 1 2
10 8 6 00001010 00001000 00000110 2 2
11 8 6 00001011 00001000 00000110 3 2
12 8 6 00001100 00001000 00000110 4 2
13 8 6 00001101 00001000 00000110 5 2
14 8 6 00001110 00001000 00000110 6 2
----------------------------------------------
10 10 8 00001010 00001010 00001000 0 2
----------------------------------------------
12 12 10 00001100 00001100 00001010 0 2
13 12 10 00001101 00001100 00001010 1 2
14 12 10 00001110 00001100 00001010 2 2
----------------------------------------------
14 14 12 00001110 00001110 00001100 0 2
----------------------------------------------
16 16 14 00010000 00010000 00001110 0 2
17 16 14 00010001 00010000 00001110 1 2
18 16 14 00010010 00010000 00001110 2 2
19 16 14 00010011 00010000 00001110 3 2
20 16 14 00010100 00010000 00001110 4 2
21 16 14 00010101 00010000 00001110 5 2
22 16 14 00010110 00010000 00001110 6 2
23 16 14 00010111 00010000 00001110 7 2
24 16 14 00011000 00010000 00001110 8 2
25 16 14 00011001 00010000 00001110 9 2
26 16 14 00011010 00010000 00001110 10 2
27 16 14 00011011 00010000 00001110 11 2
28 16 14 00011100 00010000 00001110 12 2
29 16 14 00011101 00010000 00001110 13 2
30 16 14 00011110 00010000 00001110 14 2
----------------------------------------------
18 18 16 00010010 00010010 00010000 0 2
----------------------------------------------
So when the max is not K-1, it seems to always be K-2, and K must be even.
Consider K=2**p with p>0, to simplify (that is, forget the higher bits of K, for even K). The "natural" max should be K-1, that is 2**p-1.
Example:
In binary, for K=1000, the natural max would be 111. But it can't happen if all the values we have at hand for A and B are less than K: the max for B would be 111, but then A must be smaller, so at least one bit will be lost. The max will then be 110, that is K-2.
This problem occurs when N is not much larger than 1000: if it is large enough, then we have enough values of A and B to get A&B=111. Specifically, if N is at least 1111, then with A=111 and B=1111, we are done.
When K is not a power of two, it's only slightly more complicated.
Now, you should have all necessary bits to finish.
A final check.
def p2(k):
p = 1
while k % (2 * p) == 0:
p *= 2
return p
count1 = count2 = 0
for k in range(2, 256):
print("-" * 60)
for n in range(k, 256):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
t1 = "*" if m == k - 1 else " "
if k % 2 == 0:
p = p2(k)
t2 = "*" if n <= k + p - 2 and m == k - 2 else " "
else:
t2 = " "
if t1 == t2:
count1 += 1
else:
count2 += 1
print("{:s} {:s} {:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(t1, t2, n, k, m, n, k, m, n - k, k - m))
print(count1, count2)
What to learn from this?
Final note: to get the largest power of 2 that divives K, I used a loop. There is a much better way, that you will find by considering K^(K-1) (where ^ deontes exclusive-or, as in Python).
It's the kind of bit hackery that is often useful when optimizing code. You will find other examples here and there.
Answer to the comment
The condition can be simplified:
All in all:
If N>=K|(K-1), the max is K-1, otherwise it's K-2.