Most worth with no 3 consecutive set bits

Given a non-negative integer n, discover the utmost worth that may be obtained by unsetting any set bit, such that no three consecutive bits within the ensuing integer are set bits.

Examples:

Enter: n = 2
Output: 2
Rationalization: 2’s binary type is 10, no 3 consecutive set bits are right here. So, 2 itself could be reply.

Enter: n = 7
Output: 6
Rationalization: 7’s binary type is …..00111.We will observe that 3 consecutive bits are set bits. This isn’t allowed. So, we will carry out operation of adjusting set bit to unset bit. Now, the quantity turns into 6 that’s …..00110. It satisfies the given situation. Therefore, the utmost doable worth is 6.

Strategy: To unravel the issue observe the under thought:

The concept is to first convert the given question into binary type after which traverse over the binary type of the question and verify if 3 consecutive bits are set(1) then convert the rightmost little bit of consecutive bit as unset(0) as a result of we wish most worth on the finish, for this we now have to unset least important bit which is current on the rightmost facet.

Under are the steps for the above strategy:

• Initialize an array set[] to 0, of measurement 35 to retailer the binary type of the given question.
• Covert the given question into binary type and retailer it within the array set[].
  • Run a loop from j = 30 until j ≥ 0,
    • if ((1 << j) & n), set[j] = 1.
• Initialize a variable say fin_ans to retailer the reply.
• Now run a loop over the set[] array from probably the most important bit in the direction of the least important bit.
  • Examine if the ith bit and (i-1)^th bit is ready then unset the (i-2)^th bit in order that 3 consecutive bit should not be set.
    • if (set[j] == 1), fin_ans |= (1 << j).
    • if (set[j – 1] == 1), set[j – 2] = 0.
• And likewise take the bitwiseOR operation with reply and a couple ofⁱ, so as to add the all set bit values.
  • if (set[1] == 1), fin_ans |= 2.
  • if (set[0] == 1), fin_ans |= 1.
• Return the reply.

Under is the code for the above strategy:

Time Complexity: O(1), As we’re traversing over the bits of the given question, within the worst case loop runs 32 instances because the integer restrict is 232 so we will say that point complexity is fixed.
Auxiliary Area: O(1), As we’re storing the bits of the given question in an array, within the worst case it takes 32 measurement of the array because the integer restrict is 232 so we will say that area complexity is fixed.