Problem LinksAuthor: Ankur Goel Tester: Ankur Goel Editorialist: Ankur Goel DifficultyMedium PrerequisitesFibonacci Series, Recursion ProblemThe King wants to select N common folks as solider from the Fire and Ice island in order to win the battle. He can only select odd number of people from land of fire or ice only in one go.He cannot select bunch of people consecutively from either territory.Find the number of ways the mad king could select his army. Note :The number of people in each territory is infinite. Quick ExplanationAns= 2*Fibo(N)%M ExplanationThe Problem is simply based on the Fibonacci Series. Let 0 denotes the people from Land of Ice and 1 denotes the people from Land of Fire then, the number of binary strings of length n without an even number of consecutive 0s or 1s is 2Fn. For example, out of the 16 binary strings of length 4, there are 2F4 = 6 without an even number of consecutive 0s or 1s – they are 0001, 0111, 0101, 1000, 1010, 1110. Find the Fibonacci using O(Log N) Algorithm and take the modulo M at every step, otherwise your algo may fail due to Time Complexity or due to the Overflow of Fibonacci Number beyond the range of even 64 bit int. Author's SolutionAuthor's solution can be found here Related ProblemsAnkur and Coins
This question is marked "community wiki".
asked 08 Oct '16, 20:58

He cannot select bunch of people consecutively from either territory. Then how is 0111 allowed (111 is a consecutive bunch). answered 13 Mar '18, 00:51

Let's write a recurrence for the answer. Let T0(n) be the number of valid strings ending in 0, and T1(n) be the number of valid strings ending in 1. Since n >= 1, the answer is T0(n) + T1(n). We can find some base cases. T0(1) = 1, since there is one string of length one that ends with 0, i.e., 0 T0(2) = 1, since there is one string of length two that ends with 0, i.e., 10 Now consider T0(n) for n >= 3. Given a string of length n that ends in 0, there are two cases, of which exactly one applies. The first case is that the string ends in 10, in which case dropping the 0 gives a valid string of length n  1 ending in 1. The second case is that the string ends in 000, in which case dropping the 00 gives a valid string of length n  2 ending in 0. T0(n) = T0(n  2) + T1(n  1) We observe by the symmetry of problem that T0(n) = T1(n). T0(n) = T0(n  2) + T0(n  1) This is the Fibonacci recurrence. The answer is T0(n) + T1(n) = 2 Fib(n). answered 06 Aug '18, 23:11

Hi, I am trying to find a recursive solution without making use of the Fibonacci numbers. We pass the number to the recursive function and select every odd number less than the number itself in the first layer of recursion then we make recursive calls to the number  the selected number then again repeat the process and eventually when the number left is equal to zero we increment a global counter by 1. Its kinda hard to explain.. just look at my code. The problem is that I am getting TLE help me reduce recursion calls by using memoization or other means. link to my code  https://gist.github.com/ksraj123/4aea2f088bdaeba95d7914d144556394 Sorry for replying on an old thread. I hope to receive your valuable input. answered 11 Nov '18, 03:58
