CODEWITHSUNDEEP
pythonalgorithmbit-manipulationbitwise-operatorsboolean-logic
Natalie Perret
Natalie Perret

Reputation: 9037

Find the maximum of a & b in a set s = {1, 2, ... n } lesser than a certain value k

I was playing a bit with the Python language to solve a tutorial on HackerRank, available here: https://www.hackerrank.com/challenges/30-bitwise-and

The gist of the challenge is to find the maximum of a & b where a, b ∈ s, s is the set defined such as: s = {1, 2, ... n} where a < b. Another condition is that a & b < k where 2 <= k <= n.

The given inputs are n and k.

I managed to have an O(n^2) and O(n) solutions but I am struggling to come up with an O(1) solution.

For example, here is below a dummy O(n^2) solution:

def max_and(n, k):
    if (n < k) or (k < 2):
        raise ValueError()
    else:
        res = (0, 1, 0)
        for a in range(n + 1):
            for b in range(n + 1):
                if a < b:
                    temp = a & b
                    if res[2] < temp < k:
                        res = (a, b, temp)
        return res


for n in range(2, 10):
    print(["(n = {}, k = {}) = ".format(n, k) + str(max_and(n, k)) for k in range(2, n + 1)])

I noticed that the answer is always k - 1 or k - 2 which makes sense to me.

I think the idea is that the maximum of a & b is constraint to be lesser than k and since the logical and operator cannot output a number greater than b.

Some people on HackerRank came up with a O(1) solution but I don't really get how it actually works:

a = k - 1
b = (~a) & -(~a)

if (a | b) > n:
    print (a - 1)
else:
    print (a)

Especially why b = (~a) & -(~a)

I mean I get the point that it can be changed as

Upvotes: 2

Views: 265

Answers (1)

user2357112
user2357112

Reputation: 281633

Let j = k - 1, and let unset_bit be the lowest power of two such that (j & unset_bit) == 0.

If (j | unset_bit) <= n, then we pick a = j and b = j | unset_bit for the optimal value of (a & b) == j.

If (j | unset_bit) > n, then no possible choice of a and b will give us (a & b) == j. We simply don't have two numbers to pick with all the necessary bits set. Since an even j would have given us (j | unset_bit) == j+1 <= n, we must have j odd. Then picking a = j - 1 and b = j gives us (a & b) == j - 1, the highest possible value.

The code you saw on HackerRank implements this idea. In the code you found, their a is our j, and their b is our unset_bit, computed through some bit twiddling tricks. I've used j and unset_bit instead of a and b because you've already used those letters for other meanings.

Upvotes: 1

Related Questions