Problem Links
Practice
Contest
Author: Ankur Goel
Tester: Ankur Goel
Editorialist: Ankur Goel
Difficulty
Medium
Prerequisites
Fibonacci Series, Recursion
Problem
The 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 Explanation
Ans= 2*Fibo(N)%M
Explanation
The 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 Solution
Author’s solution can be found here
Related Problems
Ankur and Coins
He cannot select bunch of people consecutively from either territory. Then how is 0111 allowed (111 is a consecutive bunch).
@vir_mis he has selcted 0 from fire and then 3 from ice. 0111 is just a representation.
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).
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.