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, 111strings satisfying the constraints:
000, 001, 010 ,100, 101So total 5 string are there.
I believe this was asked in Publicis Sapient — Jumpstart,
this 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
it is fibonacci ;-;
Could the reasoning be something like this?
Let 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.
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]; }