You are given two types of people, type A and type B. You need to place n people of any type but the condition is that no two A type people is close to each other, means [A,A,B,A,B] not possible since two A type person are close to each other. You need to find all the possible arrangement. Print the answer modulo 1e9 + 7.

Constraints

1 <= n <= 100000

Input: 3 Output: 5

Explanation: if n = 3 then possible combinations are [B,B,B] [A,B,B] [B,A,B] [B,B,A] [A,B,A]

So the answer is 5.

Is there a link to that problem?

The problem is same as finding number of n bit strings without any pair of consecutive ones. For n = 3, all strings:

`000, 001 , 010, 011, 100, 101, 110, 111`

strings satisfying the constraints:

`000, 001, 010 ,100, 101`

So total 5 string are there.

I believe this was asked in Publicis Sapient — Jumpstart,

my approachthis is a basic dp problem, where we can have states like

dp[i][0] -> number of such strings ending with A

dp[i][1] -> number of such strings ending with B

transitions will go like

dp[i][0] = dp[i-1][1] //if i_th char is A then i-1 th char has to be B

dp[i][1] = dp[i-1][0] + dp[i-1][1] // if i_th char is B then i_1th char can be anything

base case will be one character strings, so

dp[0][0] = 1

dp[0][1] = 1

something coolit is fibonacci ;-;

This problem was also in dynamic programming course, on informatics.msk.ru. If you know russian and want to learn classic dp problems, check the course out.

Could the reasoning be something like this?

More DetailsLet us answer the question how many strings of length $$$i$$$ are there that satisfy the conditions. To solve denote $$$f(i) = $$$ number of valid strings of length $$$i$$$.

Now two cases:

Thus the answer is $$$f(i) = f(i - 1) + f(i - 2)$$$, i.e. Fibonacci.

this can be done easily in math. We convert the problem this way: given all the B's already arranged, insert A's into them such that no 2 of them take the same place. It is now obvious that the answer is (number of B)+1 choose number of A places to insert them.

you can easily solve it with stars and bars,

assume z spaces like __ a1 __ a2 __ a3... __ a4 __ ,

which would be lets say, z = |a| + 1,

so what you have is b1 + b2 + b3 + ... + bz = |b|

here b1,bz >= 0 and b2,b3...b_{z-1} >= 1

so b1 + b2 + b3 + ... + bz = |b| — |a| + 1

for stars and bars we know that ,its (n + k — 1) C (r — 1)

so its (|b| — |a| + 1 + z — 1 ) C (z — 1)

which is (|b| + 1) C (|a|)

we know |b| + |a| = n

(n — |a| + 1) C |a|

you can easily find summation pattern from this

as |a| is in range [0 , n]

## include <bits/stdc++.h>

using namespace std;

## define mod 1000000007

int main() { int n; cin>>n; vectordp(n+1); dp[0]=1; dp[1]=2; for(int i=2;i<=n;i++) { dp[i]=(dp[i-2]%mod + dp[i-1]%mod)%mod; } cout<< dp[n]; }

nice but easy problem