Ninja And The Fence

Hard
0/120
profile
Contributed by
105 upvotes
Asked in company
Bajaj Electricals Ltd

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1 1
3 2
Sample Output 1 :
1
6
Explanation Of Sample Input 1 :
For the first test case, there is only one way to paint the fence. 

For the second test case, We can paint the fence with 3 posts with the following different combinations.

110
001
101
100
010
011
Sample Input 2 :
2
2 4
4 2
Sample Output 2 :
16
10
Hint

Can we generalize the formula for every 'N'?

Approaches (4)
Recursive Brute Force

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):

  1. If 'N' == 1 return 'K'.
  2. If 'N' == 2 return 'mul(K, K)'.
  3. If 'N' == 3 return 'mul(K, mul((K + 1), (K - 1)))'.
  4. Else return 'add(mul(solve(N - 1, K), (K - 1)), mul(solve(N - 2, K), (K - 1)))'.

 

numberOfWays(N, K)

  1. Return 'solve(N, K)'
Time Complexity

O(2^N), where 'N' and 'K' are input integers.

 

As we are using the recursion and in every recursion call, there are two separate recursion calls; hence the time complexity will be O(2^N).

Space Complexity

O(1)

 

As we are using the constant extra space, the space complexity will be O(1)

Code Solution
(100% EXP penalty)
Ninja And The Fence
Full screen
Console