Infosys sample question

Bitwise subsequence

You have an array A of N integers A1 A2 … An. Find the longest increasing subsequence Ai1 Ai2 … Ak
(1 <= k <= N) that satisfies the following condition:
For every adjacent pair of numbers of the chosen subsequence Ai[x] and Ai[x+1] (1 < x < k), the
expression( Ai[x] & Ai[x+1] ) * 2 < ( Ai[x] | Ai[x+1] ) is true
Note: ‘&’ is the bitwise AND operation, ’ | ’ is the bit-wise OR operation

Input:

The first line contains an integer, N, denoting the number of elements in A.
Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing Ai.

Sample cases:
Input
5 //size of array
15
6
5
12
1
output:2
explanation:
One possible subsequence is: 5 12

Input:
7 //size
17
16
12
2
8
17
17
output:3
explanation: One possible subsequence is:2 8 17