You are given an integer K.
A function F is defined over non-negative integers as the following:
for i such that the given conditions hold true:
Determine the number of non-negative integers x such that
| = bitwise or
& = bitwise and
Example for K = 6, possible x is 0, 1, 2, 3 and 4 as F(0) = 0
F(1) = 1
F(2) = 2
F(3) = 6
F(4) = 4
So, the answer is 5.
Constraints
It was asked in nokia coding hackthon.
I wasn't able to find any pattern to approach any optimal solution. How would you approach this problem?