And It's Non-Zero (Codeforces 1615B)
Tags: Greedy, bitmasks

You are given an array consisting of all integers from $$$[l, r]$$$ inclusive. For example, if $$$l = 2$$$ and $$$r = 5$$$, the array would be $$$[2, 3, 4, 5]$$$. What's the minimum number of elements you can delete to make the bitwise AND of the array non-zero?A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.

Input: The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ cases follow.The first line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq 2 \cdot 10^5$$$) — the description of the array.

Output: For each test case, output a single integer — the answer to the problem.

Note: In the first test case, the array is $$$[1, 2]$$$. Currently, the bitwise AND is $$$0$$$, as $$$1\ \& \ 2 = 0$$$. However, after deleting $$$1$$$ (or $$$2$$$), the array becomes $$$[2]$$$ (or $$$[1]$$$), and the bitwise AND becomes $$$2$$$ (or $$$1$$$). This can be proven to be the optimal, so the answer is $$$1$$$.In the second test case, the array is $$$[2, 3, 4, 5, 6, 7, 8]$$$. Currently, the bitwise AND is $$$0$$$. However, after deleting $$$4$$$, $$$5$$$, and $$$8$$$, the array becomes $$$[2, 3, 6, 7]$$$, and the bitwise AND becomes $$$2$$$. This can be proven to be the optimal, so the answer is $$$3$$$. Note that there may be other ways to delete $$$3$$$ elements.

Sample Inputs:
5
1 2
2 8
4 5
1 5
100000 200000

Sample Outputs:
1
3
0
2
31072

Solution (Python):
import math

def getcount(n, k):
    res = n >> k + 1 << k
    if n >> k & 1:
        res += n & (1 << k) - 1
    return res
t = int(input())
for _ in range(t):
    (l, r) = list(map(int, input().split()))
    k = int(math.log(l, 2))
    print(min(r - l + 1 - getcount(r + 1, k) + getcount(l, k), r - l + 1 - getcount(r + 1, k + 1) + getcount(l, k + 1)))

Solution (Python):
from math import log2, floor
for t in range(int(input())):
    (a, b) = map(int, input().split())
    maxi = 0
    for i in range(0, floor(log2(b)) + 1):
        temp = 2 ** i
        lower = a // temp
        if lower % 2 == 1:
            ans = temp * lower - a
        else:
            ans = 0
            lower = lower + 1
        higher = b // temp
        if higher % 2 == 1:
            ans = ans + (b - temp * higher + 1)
        else:
            higher = higher + 1
        ans += (higher * temp - lower * temp) // 2
        maxi = max(ans, maxi)
    print(b - a - maxi + 1)

Solution (Python):
from sys import stdin
from bisect import bisect_left

def brute():
    results = []
    for _ in range(int(stdin.readline().strip())):
        (l, r) = map(int, stdin.readline().strip().split())
        if l == r:
            results.append(0)
            continue
        n = len(bin(r))
        B = []
        for x in range(l, r + 1):
            b = bin(x)[2:]
            b = '0' * (n - len(b)) + b
            B.append(bytearray(b, 'utf-8'))
        ord1 = ord('1')
        cnt = [x.count(ord1) for x in list(zip(*B))]
        results.append(r - l + 1 - max(cnt))
    print('\n'.join(map(str, results)))

def getcount(n, k):
    res = n >> k + 1 << k
    if n >> k & 1:
        res += n & (1 << k) - 1
    return res

def solve():
    results = []
    pows2 = [1, 2]
    x = 4
    while x <= 10 ** 19:
        pows2.append(x)
        x *= 2
    for _ in range(int(stdin.readline().strip())):
        (l, r) = map(int, stdin.readline().strip().split())
        if l > r:
            (l, r) = (r, l)
        if l == r:
            results.append(0)
            continue
        pos = bisect_left(pows2, r)
        n = r - l + 1
        ans = n - (min(pows2[pos] - 1, r) - max(pows2[pos - 1], l) + 1)
        if pows2[pos - 1] > l:
            ans = min(ans, n - (pows2[pos - 1] - max(pows2[pos - 2], l)))
        for i in range(len(bin(r)[2:])):
            a = getcount(l, i)
            b = getcount(r + 1, i)
            ans = min(ans, r - l + 1 - (b - a))
        results.append(ans)
    print('\n'.join(map(str, results)))
if __name__ == '__main__':
    solve()