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