The Question in the link below was asked in the Code Monk Round at hackerearth
https://www.hackerearth.com/problem/algorithm/vaishu-and-best-friends/

I decoded it and found that the answer should be

**(all possible combination - All subsequences with alernating 0s and 1s)**

So the Problem narrows down to finding the number of possible subsequences with alternating 0s and 1s

here is my approach of finding all possible subsequences with alternating 0s and 1s

```
dp[1][1] = 1;
dp[0][1] = 0;
for(int i = 2; i <= 1000000; i++){
if(i % 2 == 1){
dp[1][i] = (dp[0][i-1] + dp[1][i-1] + 2)%M;
dp[0][i] = (dp[0][i-1]%M);
}else{
dp[0][i] = (dp[1][i-1] + dp[0][i-1] + 1)%M;
dp[1][i] = (dp[1][i-1]%M);
}
}
```

Here dp[0][i] indicates all the subsequences till now ending at a 0

and dp[1][i] indicates all the subsequences till now ending at a 1

The sum of dp[0][n] + dp[1][n] will tell all alternating subsequences

But i am getting a wrong answer.
Please Point out what is wrong

Here is the Full code

```
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long dp[2][1000005];
long long power[1000005];
void precompute(){
power[0] = 1;
power[1] = 2;
dp[1][1] = 1;
dp[0][1] = 0;
for(int i = 2; i <= 1000000; i++){
power[i] = power[i-1]*2;
power[i] %= M;
if(i&1){
dp[1][i] = (dp[0][i-1] + dp[1][i-1] + 2)%M;
dp[0][i] = (dp[0][i-1]%M);
}else{
dp[0][i] = (dp[1][i-1] + dp[0][i-1] + 1)%M;
dp[1][i] = (dp[1][i-1]%M);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
precompute();
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("&d", &n);
long long ans = ((M + ((power[n] - dp[0][n-1] + M) % M) - dp[1][n-1]))%M ;
ans += M;
ans %= M;
printf("%d\n", ans);
}
return 0;
}
```

asked
**08 Apr '17, 12:33**

4★ravidelcj

101●4●11

accept rate:
16%