Last Updated: 11 Dec, 2021
Ninja And The Fence
Hard
Asked in company
Ninja has given a fence, and he gave a task to paint this fence. The fence has 'N' posts, and Ninja has 'K' colors. Ninja wants to paint the fence so that not more than two adjacent posts have the same color.
Ninja wonders how many ways are there to do the above task, so he asked for your help.
Your task is to find the number of ways Ninja can paint the fence. Print the answer modulo 10^9 + 7.
Example:
Input: 'N' = 3, 'K' = 2
Output: 6
Say we have the colors with the numbers 1 and 0. We can paint the fence with 3 posts with the following different combinations.
110
001
101
100
010
011
Input Format :
The first line of input contains an integer 'T', denoting the number of test cases.
Each test case will contain two integers 'N' and 'K' denoting the number of posts on the fence and the number of colors Ninja has.
Output format :
For each test case, print the number of ways modulo 10^9 + 7 to paint the fence.
Output for each test case will be printed in a separate line.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^5
Time Limit: 1 sec
Approaches
Approach: Say the function 'solve(n)' calculates how many ways to paint a fence with 'N' points and 'K' colors. we want to figure out the relationship between 'solve(n)' for 'N' points and with fewer points fence solutions like 'solve(n - 1)', 'solve(n - 2)', 'solve(n - 3)'.
Assume that both 'solve(n - 1)' and 'solve(n - 2)' are valid results, which means the last 2nd color is mush not equivalent to the last 3rd color. And then, the previous three colors have (k - 1) different choices.
Then the formula will be
solve(n) = solve(n - 1) * (k - 1) - solve(n - 2) * (k - 1)
We will use the above formula to find the answer recursively.
Algorithm :
Define the function 'add', which will return the modulo addition of two numbers.
Define the function 'mul', which will return modulo multiplication of two numbers.
// Function to get the number of ways to paint the fence with 'N' posts with 'K' colors available.
solve(N, K):
- If 'N' == 1 return 'K'.
- If 'N' == 2 return 'mul(K, K)'.
- If 'N' == 3 return 'mul(K, mul((K + 1), (K - 1)))'.
- Else return 'add(mul(solve(N - 1, K), (K - 1)), mul(solve(N - 2, K), (K - 1)))'.
numberOfWays(N, K)
- Return 'solve(N, K)'
Approach: In the above approach, we are repetitively calling the recursive calls; instead, we can store the partial results in the 'DP' array and use it for further recursive calls. It will save time by making it time-efficient.
Algorithm :
Define the function 'add', which will return the modulo addition of two numbers.
Define the function 'mul', which will return modulo multiplication of two numbers.
// Function to get the number of ways to paint the fence with 'N' posts with 'K' colors available.
solve(N, K, DP):
- If 'N' == 1 return 'K'
- If 'N' == 2 return 'mul(K, K)'
- If 'N' == 3 return 'mul(K, mul((K + 1), (K - 1)))'
- If 'DP[N]' != -1 return 'DP[N]'
- Update 'DP[N]' with 'add(mul(solve(N - 1, K, DP), (K - 1)), mul(solve(N - 2, K, DP), (K - 1)))'
- Return 'DP[N]'
numberOfWays(N, K)
- Initialize the 'DP' vector of size 'N + 1' with -1.
- Return 'solve(N, K, DP)'
Approach: In the above approach, we will do the same as we did in the previous approach, but instead of calling recursion, we will do it iteratively by calculating the results from the starting position.
Algorithm :
Define the function 'add', which will return the modulo addition of two numbers.
Define the function 'mul', which will return modulo multiplication of two numbers.
numberOfWays(N, K)
- Initialize the 'DP' vector of size 'N + 1' with 0.
- Update 'DP[1]' with 'K'
- Update 'DP[2]' with 'mul(K, K)'
- Run a loop from 3 to 'N' with variable 'I'
- Update 'DP[i]' with 'mul((K - 1), add(DP[i - 1], DP[i - 2]))'
- Return 'DP[N]'
Approach: In the above approach, we will space optimize the above solution; instead of using the 'DP' table we will use the variable. it will make it a constant time solution.
As we can see, we only require the last two-step results for each step. Hence we can store them only and use them later.
Algorithm :
Define the function 'add', which will return the modulo addition of two numbers.
Define the function 'mul', which will return modulo multiplication of two numbers.
numberOfWays(N, K)
- Initialize the variable 'answer' with 'K'
- Initialize the variable 'same' with 0 and 'diff' with 'K'
- Run a loop from 2 to 'N' with variable 'I'
- Update 'same' with 'diff'
- Update 'diff' with 'mul(answer, (K - 1))'
- Update 'answer' with 'add(same, diff)'
- Return 'answer'