Discover all M in vary [2, N] such that bitwise OR until M is the same as the worth until M-1

Given an integer N, the duty is to search out all attainable integer M within the vary [2, N] such that the bitwise OR of all constructive values until M is similar because the bitwise OR of all constructive values until M-1.

Examples:

Enter: N = 4
Output: 1
Rationalization: Bitwise OR until 3 = 1 | 2 | 3 = 3.
Bitwse OR until 2 = 1 | 2 = 3.

Enter: N = 7
Output: 4

Method: The method to unravel this drawback relies on the next remark:

Contemplate p(x) to the bitwise OR until x. So p(x) = 1 | 2 | 3 | . . . | (x-1) | x
Given p(x) = 1 | 2 | 3 | . . . | x – 1 | x. Subsequently, p(x + 1) can be totally different from p(x) if there’s a new “1” bit in (x + 1) that isn’t current within the binary sequence of p(x).

Now, allow us to observe the sample:

Decimal Quantity	Binary Quantity
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001

We will see {that a} new “1” bit that hasn’t beforehand appeared within the vary [1, x] seems at each energy of two.
As such,  p(x) = 1 | 2 | 3 | . . . | x – 1 | x 
                     = 2^a+1 – 1, the place a = log₂x. 
This suggests that, for a given a, there can be ( 2^{a + 1} – 2^a – 1 ) values of x the place p(x) = p(x – 1).

Comply with the step beneath to unravel this drawback:

• Calculate a = log₂N. 
• Iterate via the powers (say utilizing variable exp) of two from 1 to a and increment ans (initially 0) by ( 2 ^{exp + 1} – 2^exp – 1 ).
• Lastly, depend for the pairs between N and 2^a by including (n – 2^a) to ans.

Time Complexity: O(log₂N)
Auxiliary Area: O(1)