Smallest number whose set bits are MINIMUM in a given range-CodePudding

Given a positive integer ‘l‘ and ‘r‘. Find the smallest number ‘n‘ such that l <= n <= r and count of the number of set bits(number of ‘1’s in binary representation) is MINIMUM as possible.

This article: https://www.geeksforgeeks.org/smallest-number-whose-set-bits-maximum-given-range/ gives the smallest number with maximum set bits. But I need the smallest number in [l, r] with minimum set bits.

We can simply do this in linear time. But, I am looking for an Optimized Approach that accepts--

Time complexity: O(log(n))

Auxiliary space: O(1) or O(n)

Constraints:

1 <= l <= r <= 10^18

Below is my Code--

import math

l, r = map(int, input().split())
if l <= 2: print(l)
else:
    x1 = math.log(l, 2)
    x2 = math.log(r, 2)
    x3 = int(math.pow(2, math.ceil(x1)))
    
    if x1 == x2 or x3 > r:
       cnt = 32
       for i in range(l, r 1):
            s = bin(i).replace("0b", "")
            cnt1 = s.count('1')
            if cnt1 < cnt:
               cnt = cnt1
               ans = i
           
    else:
        ans = x3
        
    print(and)

I need to optimize the for loop in the above python code. Thank You.

CodePudding user response：

Here's the idea of a logarithmic approach.

The main concept behind it is the following: To reduce the number of set bits in the binary representation of a number while you can increase it up to an upper bound you must add a number equal to the value of the least significant set bit to the original number. This operation pushes the set bit to the left. When 2 set bits become adjacent, adding the value equal to the least significant bit effectively reduces the 2 set bits into one set bit while pushing it to the left.

given 01100
add   00100
gives 10000

another example:
given 00101
add   00001
gives 00110
add   00010
gives 01000

The above concept motivates the following algorithm:

def num_of_set_bits(num):
  res = 0
  while num:
    res  = 1
    num = (num - 1) & num
  return res

def min_set_bits(low, high):
  res = num_of_set_bits(low)

  while low < high:
    low  = (low & -low) # two's complement; unsets all except for the LSB
    if low <= high:
      res = min(res, num_of_set_bits(low))
  return res

Time complexity: O(log high * num of max set bits) Space complexity: O(1)

There are some optimizations that can be done to the algorithm. For instance, if the number of set bits of low is 1, just return one. Or, we can look to the left of the LSB and if that bit is not set, we won't count the bits again since the operation won't reduce the number of bits. A further optimization is to reduce the number of bits by one automatically when we see that th left bit of LSB is set. We don't to count the number of bits any more. This reduces the Time complexity effectively to O(log high).

One note of caution at the end: I'm not 100% sure about this algorithm since I havn't read it somewhere. I came up with it myself. I don't have a fully working proof but also no counter examples. Intuitively, it looks corrct to me but intuition has mislead me a lot of times. Any feedback or counter examples are appreciated.

CodePudding user response：

Just for fun, here's a fast one-line solution (well, two lines including the def, but all the interesting stuff is in a single line) in Python. I'll unpack it a bit further down.

def fewest_set_bits_obfuscated(l, h):
    return (h:=(l:=l-1)&-1<<(l^h).bit_length())|1<<(l^h).bit_length()

Example usage:

>>> fewest_set_bits_obfuscated(617, 725)
640

Before we attempt to explain what's going on above, let's check that the code above does actually give the correct answer. Here's an obviously-correct but inefficient algorithm (though still a one-liner) to compute the first value with the smallest number of set bits in the range [l, h]. It makes use of the int.bit_count method, which is new in Python 3.10:

def fewest_set_bits_brute_force(l, h):
    return min(range(l, h 1), key=int.bit_count)

In case you don't have Python 3.10 available, here's an even slower version that counts the 1 bits manually:

def fewest_set_bits_brute_force(l, h):
    return min(range(l, h 1), key=lambda n: bin(n).count("1"))

Now we can double check that fewest_set_bits_obfuscated and fewest_set_bits_brute_force give the same result for a range of inputs:

MAX = 1000
for high in range(1, MAX 1):
    for low in range(1, high 1):
        ans_obfuscated = fewest_set_bits_obfuscated(low, high)
        ans_brute_force = fewest_set_bits_brute_force(low, high)
        assert ans_obfuscated == ans_brute_force, f"failed for {low}, {high}"

The above code will take a bit of time to run (around 41 seconds on my laptop), but it should complete without any of the asserts failing.

Now it's time to unpack the original one-line solution. First, let's rewrite that solution a bit:

def fewest_set_bits_deobfuscated(low, high):
    low -= 1
    non_matching_length = (low ^ high).bit_length()
    common = low & (-1 << non_matching_length)
    match_low = low ^ common
    return common | 1 << match_low.bit_length()

Here we're performing exactly the same operations, in exactly the same order, as in the one-line version, but we've renamed the parameters, given names to some of the intermediate values, and unpacked the uses of the := "walrus" operator.

The main idea here is that if you look at the binary expansions of low and high, there's some initial portion of those binary expansions that matches; after that initial portion, the expansions diverge. Our result must start with that same initial portion that low and high have, and then we can simply fill in the rest by adding just one more 1 bit in the right position.

For example, if low=1641 and high=1749 then the binary expansions are 0b11001101001 and 0b11011010101. The common initial portion consists of the first (i.e. most significant) three bits: 110. After those first three bits, the next bit for low is a 0, and the next bit for high is a 1. Every integer between low and high must also start with 110, in that same position, and the number we're after is 0b11010000000, or 1664.

The first three lines of the function above find the common portion, 0b11000000000, or 1536 in decimal. low ^ high finds the bits that don't match between low and high, then the bit_length() call tells us the length of the non-matching portion (which I'll also call the trailing portion). Then -1 << non_matching_length gives us a mask that can be used to extract the matching portion (common).

For the remaining bits, we simply want to replace the trailing portion of low (which is match_low in the function) with the next higher power of two, and that's what 1 << match_low.bit_length() gives.

The above isn't quite right, because what we actually want to do is find the next power of two that's larger than or equal to the trailing portion of low. But it turns out to be slightly easier to compute the next power of two that's strictly larger than the trailing portion of low. Because of this, we compensate right at the beginning of the function by decrementing low, so that we're actually looking for a solution in the half-open interval (low, high].