# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Lavish

Tester: Aryan, Takuki Kurokawa

Editorialist: Pratiyush Mishra

# DIFFICULTY:

Simple

# PREREQUISITES:

Highest power of 2 less than or equal to given number

# PROBLEM:

Chef was recently studying the Bitwise OR operation, and stumbled upon the following problem:

Let F(i)=1 \;| \;2\; |\; 3\; |\; … |\; i, where | denotes bitwise OR.

You are given an integer N. Find the number of distinct i such that 2≤i≤N and F(i)=F(i−1).

# EXPLANATION

Note that F(i) represents the bitwise OR of integers from 1 to i. Thus F(i) changes when a new “1” is introduced to the already existing binary sequence. We calculate the number of i’s at which F(i) changes and subtract the count from N.

Consider i = 1, 2, 4, 8 ....

A new bit is introduced in each such i.

We need to find the highest power of $2 that is less than N. Let it be x. Then, the answer would be N-x-1.

# TIME COMPLEXITY:

The above calculation can be done in roughly constant time. Hence, the solution has a time complexity of O(1).

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester-1’s Solution

Tester-2’s Solution