# RSLN2205 - Editorial

Subsequence and Bitwise &

Setter, Tester & Editorialist: Tushar Gupta

Easy-Medium

# PREREQUISITES

Dynamic Programming, Bitwise Operations

# PROBLEM

You are given a list A of length N of non-negative integers. You need to find the length of the longest subsequence of A such that the binary representation of bitwise and of all of its elements contains at least K set bits.

# EXPLANATION

First, we use dynamic programming to find out the maximum possible length of all such subsequences that the bitwise & of all its elements contain at least K set bits. Then, we just need to calculate the maximum among all such lengths.

# TIME COMPLEXITY

The worst-case time complexity is O(N*128) per test case.

# SOLUTION

Tushar Gupta
``````#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while ( t-- ) {
int n, k;
cin >> n >> k;
int x;
int ans[128];
memset ( ans, 0, sizeof ( ans ) );
while ( n-- ) {
cin >> x;
for ( int i = 0; i < 128; i++ ) {
if ( ans[i] > 0 ) {
int nd = x & i;
ans[nd] = max ( ans[nd], ans[i] + 1 );
}
}
ans[x] = max ( ans[x], 1 );
}
int mx = 0;
int kk = 0;
while ( kk < 128 ) {
if ( __builtin_popcount ( kk ) >= k ) {
mx = max ( ans[kk], mx );
}
kk++;
}
cout << mx << '\n';
}
}
``````