Day 29: HackerRank 30 Days Of Code Solution | Bitwise AND

The last challenge of HackerRank's 30 Days of Code is about the bitwise AND operator. You can pass it with two nested loops, and many people do. But there is a neat observation that answers each test case in constant time, and working it out teaches you how to reason about bits instead of just trying every pair.

Bit tricks come up often in interviews, especially questions like "is this a power of two" or "what is the lowest set bit". This problem is a gentle way to build that thinking.

Problem

Take the set of numbers from 1 to N. Choose two different numbers A and B from it, with A < B. Among all such pairs, find the largest value of A & B (bitwise AND) that is strictly less than a given K.

Input format: the first line has T, the number of test cases. Each of the next T lines has two integers, N and K.

Output format: for each test case, print the answer on its own line.

Constraints: 1 <= T <= 10^3, 2 <= N <= 10^3, 2 <= K <= N.

Input
3
5 2
8 5
2 2

Output
1
4
0

For N = 5 and K = 2, the possible AND values are 0, 1, 2 and 4. The only ones below 2 are 0 and 1, so the answer is 1.

Approach

The simple way. Try every pair, compute A & B, and keep the largest that is below K. With N = 1000 that is about 500,000 pairs per test, and with 1000 tests about 5 x 10^8 operations. It passes on HackerRank, but only just, and it does not teach much.

The better way. The best we can hope for is K - 1. So ask: is there a pair whose AND is exactly K - 1?

1. Let a = K - 1. If we use a itself as A, we need a larger B that contains every 1-bit of a. Then a & B equals a.
2. The smallest number larger than a that contains all its bits is a | (a + 1). Adding 1 flips the lowest 0-bit of a to 1, and OR-ing keeps everything else. Since a + 1 = K, this is (K - 1) | K.
3. If (K - 1) | K <= N, that B exists in the set and the answer is K - 1.
4. Otherwise the answer is K - 2.

Why is K - 2 always possible in the second case? If K - 1 were even, its lowest bit would be 0, and (K - 1) | K would just be K, which is at most N. So the second case only happens when K - 1 is odd. Then K - 2 is even, and (K - 2) & (K - 1) = K - 2, with both numbers inside the set.

Dry run. N = 8, K = 5: a = 4 (100 in binary), 4 | 5 = 5 (101), and 5 <= 8, so the answer is 4. N = 5, K = 2: a = 1, 1 | 2 = 3, and 3 <= 5, so the answer is 1. N = 2, K = 2: 1 | 2 = 3 is more than 2, so the answer is K - 2 = 0.

Solution in Java

The older code on this page used the double loop. It was correct, but it started A at 0, which is not in the set (harmless, since anything AND 0 is 0), and it did roughly half a billion operations in the worst case. The version below is O(1) per test.

import java.util.Scanner;

public class Solution {

    // Largest A & B (1 <= A < B <= n) that is strictly less than k.
    static int maxAnd(int n, int k) {
        int a = k - 1;              // the best value we could hope for
        // a & B == a needs a B > a that contains every 1-bit of a.
        // The smallest such B is a | (a + 1), and a + 1 is just k.
        if ((a | k) <= n) {
            return a;
        }
        return k - 2;               // always reachable when the check above fails
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            out.append(maxAnd(n, k)).append('\n');
        }
        System.out.print(out);
    }
}

Because a formula is easy to get subtly wrong, I checked it against the brute-force double loop for every N from 2 to 300 and every valid K. There were no mismatches. A few extra cases: 1000 1000 gives 998, 7 4 gives 3 (3 AND 7), and 6 6 gives 4 (4 AND 5).

Output

1
4
0

Complexity

Time: O(1) per test case, so O(T) overall. The brute force is O(N^2) per test.

Space: O(1).

Common mistakes

• Using && instead of &. && is logical AND on booleans and will not compile with ints in Java. & works bit by bit.
• Forgetting operator precedence. In Java, a | k <= n is read as a | (k <= n) and fails to compile. Always bracket bitwise expressions: (a | k) <= n.
• Allowing A equal to B. A & A is just A, which would make the problem trivial and wrong. The two numbers must be different.
• Using <= K. The answer must be strictly less than K.

Related: Day 10: Binary Numbers is a good warm-up on binary, and Day 28: RegEx, Patterns, and Intro to Databases is the previous day.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice