Ninja And The Fence
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

Question

Ninja And The Fence

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

Accepted Answer

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

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

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(2^n)Explanation:

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

Accepted Answer

Recursive DP Solution

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

Space Complexity: O(n)Explanation:

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

As we are using the extra 'DP' array of linear size and also we are using the recursion with maximum linear stack size, the space complexity will be O(N)

Time Complexity: O(n)Explanation:

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

As we are using the recursion and there will be at max 'N' recursive calls because of memoization, the time complexity will be O(N)

Python (3.5)

'''

    Time complexity: O(N)

    Space complexity: O(N)



    Where 'N' and 'K' are input integers.

'''



# Driver function to get the modular addition.

from typing import List





def add(a: int, b: int) -> int:

    mod = pow(10, 9) + 7

    return ((a % mod) + (b % mod)) % mod





# Driver function to get the modular multiplication.

def mul(a: int, b: int) -> int:

    mod = pow(10, 9) + 7

    return ((a % mod) * (b % mod)) % mod



# Function to get the number of ways to paint the fence with 'N' posts and 'K' colors.





def solve(n: int, k: int, dp: List[int]) -> int:



    # Checking for the base conditions.

    if (n == 1):

        return k



    if (n == 2):

        return mul(k, k)



    if (n == 3):

        return mul(k, mul((k + 1), (k - 1)))



    #  If current state is already visited then return the 'DP[N]'.

    if (dp[n] != -1):

        return dp[n]



    # Updating the answer according to the calculated formula.

    dp[n] = add(mul(solve(n - 1, k, dp), (k - 1)),

                mul(solve(n - 2, k, dp), (k - 1)))

    return dp[n]





def numberOfWays(n: int, k: int) -> int:



    # Initializing the 'DP' array.

    dp = [-1 for i in range(n + 1)]

    return solve(n, k, dp)

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(N)



    Where 'N' and 'K' are input integers.

*/



// Driver function to get the modular addition.

int add(int a, int b) {

    int mod = 1e9 + 7;

    return ((a % mod) + (b % mod)) % mod;

}



// Driver function to get the modular multiplication.

int mul(int a, int b) {

    int mod = 1e9 + 7;

    return ((a % mod) * 1LL * (b % mod)) % mod;

}



// Function to get the number of ways to paint the fence with 'N' posts and 'K' colors.

int solve(int n, int k, vector &dp) {

    // Checking for the base conditions.

    if (n == 1) {

        return k;

    }

    if (n == 2) {

        return mul(k, k);

    }

    if (n == 3) {

        return mul(k, mul((k + 1), (k - 1)));

    }

    // If current state is already visited then return the 'DP[N]'.

    if (dp[n] != -1) {

        return dp[n];

    }

    // Updating the answer according to the calculated formula.

    dp[n] = add(mul(solve(n - 1, k, dp), (k - 1)), mul(solve(n - 2, k, dp), (k - 1)));

    return dp[n];

}



int numberOfWays(int n, int k) {

    // Initializing the 'DP' array.

    vector dp(n + 1, -1);

    return solve(n, k, dp);

}

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space complexity: O(N)

    Where 'N' and 'K' are input integers.
*/

public class Solution {
    public static int numberOfWays(int n, int k) {
        // Initializing the 'DP' array.
        int[] dp = new int[n + 1];
        for(int i = 0; i <= n; i++){
            dp[i] = -1;
        }

        return solve(n, k, dp);
    }

    // Function to get the number of ways to paint the fence with 'N' posts and 'K' colors.
    public static int solve(int n, int k, int[] dp) {
        // Checking for the base conditions.
        if (n == 1) {
            return k;
        }

        if (n == 2) {
            return mul(k, k);
        }

        if (n == 3) {
            return mul(k, mul((k + 1), (k - 1)));
        }

        // If current state is already visited then return the 'DP[N]'.
        if (dp[n] != -1) {
            return dp[n];
        }

        // Updating the answer according to the calculated formula.
        dp[n] = add(mul(solve(n - 1, k, dp), (k - 1)), 
            mul(solve(n - 2, k, dp), (k - 1)));
        
        return dp[n];
    }


    // Driver function to get the modular addition.
    public static int add(int a, int b) {
        int mod = (int)1e9 + 7;
        return (int)(((long)(a % mod) + (b % mod)) % mod);
    }

    // Driver function to get the modular multiplication.
    public static int mul(int a, int b) {
        int mod = (int)1e9 + 7;
        return (int)(((long)(a % mod) * (b % mod)) % mod);
    }
}

Accepted Answer

Iterative DP Solution

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]'

Space Complexity: O(n)Explanation:

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

As we are using the extra 'DP' array of linear size, the space complexity will be O(N)

Time Complexity: O(n)Explanation:

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

As we are iterating over the array of size 'N' the time complexity will be O(N)

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(N)



    Where 'N' and 'K' are input integers.

*/



// Driver function to get the modular addition.

int add(int a, int b) {

    int mod = 1e9 + 7;

    return ((a % mod) + (b % mod)) % mod;

}



// Driver function to get the modular multiplication.

int mul(int a, int b) {

    int mod = 1e9 + 7;

    return ((a % mod) * 1LL * (b % mod)) % mod;

}



int numberOfWays(int n, int k) {

    // Initializing the 'DP' array.

    vector dp(n + 1, 0);

    // Updating the initial states.

    dp[1] = k;

    dp[2] = mul(k, k);

    // Looping over from 3 to 'N'.

    for (int i = 3; i <= n; i++) {

        // Updating the 'DP' state.

        dp[i] = mul((k - 1), add(dp[i - 1], dp[i - 2]));

    }

    // Returning the result.

    return dp[n];

}

Python (3.5)

'''

    Time complexity: O(N)

    Space complexity: O(N)



    Where 'N' and 'K' are input integers.

'''



# Driver function to get the modular addition.





def add(a: int, b: int) -> int:

    mod = pow(10, 9) + 7

    return ((a % mod) + (b % mod)) % mod





# Driver function to get the modular multiplication.

def mul(a: int, b: int) -> int:

    mod = pow(10, 9) + 7

    return ((a % mod) * (b % mod)) % mod





def numberOfWays(n: int, k: int) -> int:

    #  Initializing the 'DP' array.

    dp = [0 for i in range(n + 2)]



    # Updating the initial states.

    dp[1] = k

    dp[2] = mul(k, k)



    # Looping over from 3 to 'N'.

    for i in range(3, n + 1):

        #  Updating the 'DP' state.

        dp[i] = mul((k - 1), add(dp[i - 1], dp[i - 2]))



    # Returning the result.

    return dp[n]

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space complexity: O(N)

    Where 'N' and 'K' are input integers.
*/

public class Solution {
    public static int numberOfWays(int n, int k) {
        if(n == 1){
            return k;
        }

        // Initializing the 'DP' array.
        int[] dp = new int[n + 1];

        // Updating the initial states.
        dp[1] = k;
        dp[2] = mul(k, k);

        // Looping over from 3 to 'N'.
        for (int i = 3; i <= n; i++) {
            // Updating the 'DP' state.
            dp[i] = mul((k - 1), add(dp[i - 1], dp[i - 2]));
        }

        // Returning the result.
        return dp[n];
    }

    // Driver function to get the modular addition.
    public static int add(int a, int b) {
        int mod = (int)1e9 + 7;
        return (int)(((long)(a % mod) + (b % mod)) % mod);
    }

    // Driver function to get the modular multiplication.
    public static int mul(int a, int b) {
        int mod = (int)1e9 + 7;
        return (int)(((long)(a % mod) * (b % mod)) % mod);
    }
}

Accepted Answer

Iterative Constant Space Solution

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'

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n)Explanation:

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

As we are iterating 'N' times the time complexity will be O(N)

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space complexity: O(1)

    Where 'N' and 'K' are input integers.
*/

public class Solution {
    public static int numberOfWays(int n, int k) {
        // Initializing the variables 'answer', 'same' and 'diff'.
        int answer = k;
        int same = 0, diff = k;

        // Looping over from 2 to 'N'.
        for (int i = 2; i <= n; i++) {

            // Updating the 'same', 'diff' and 'answer'.
            same = diff;
            diff = mul(answer, (k - 1));
            answer = add(same, diff);
            
        }

        // Returning the 'answer'.
        return answer;
    }

    // Driver function to get the modular addition.
    public static int add(int a, int b) {
        int mod = (int)1e9 + 7;
        return (int)(((long)(a % mod) + (b % mod)) % mod);
    }

    // Driver function to get the modular multiplication.
    public static int mul(int a, int b) {
        int mod = (int)1e9 + 7;
        return (int)(((long)(a % mod) * (b % mod)) % mod);
    }
}

Python (3.5)

'''

    Time complexity: O(N)

    Space complexity: O(1)



    Where 'N' and 'K' are input integers.

'''





# Driver function to get the modular addition.

def add(a:int, b:int)->int:

    mod = pow(10,9) + 7

    return ((a % mod) + (b % mod)) % mod





# Driver function to get the modular multiplication.

def mul(a:int, b:int)->int:

    mod = pow(10,9) + 7;

    return ((a % mod) * (b % mod)) % mod





def numberOfWays(n:int,k:int)->int:



    # Initializing the variables 'answer', 'same' and 'diff'.

    answer = k;

    same = 0

    diff = k



    # Looping over from 2 to 'N'.

    for i in range(2, n + 1):

        # Updating the 'same', 'diff' and 'answer'.

        same = diff;

        diff = mul(answer, (k - 1));

        answer = add(same, diff);

    

    # Returning the 'answer'.

    return answer

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(1)



    Where 'N' and 'K' are input integers.

*/



// Driver function to get the modular addition.

int add(int a, int b) {

    int mod = 1e9 + 7;

    return ((a % mod) + (b % mod)) % mod;

}



// Driver function to get the modular multiplication.

int mul(int a, int b) {

    int mod = 1e9 + 7;

    return ((a % mod) * 1LL * (b % mod)) % mod;

}



int numberOfWays(int n, int k) {

    // Initializing the variables 'answer', 'same' and 'diff'.

    int answer = k;

    int same = 0, diff = k;

    // Looping over from 2 to 'N'.

    for (int i = 2; i <= n; i++) {

        // Updating the 'same', 'diff' and 'answer'.

        same = diff;

        diff = mul(answer, (k - 1));

        answer = add(same, diff);

    }

    // Returning the 'answer'.

    return answer;

}

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

Output format :

Note :

Constraints :

Top Bajaj Finserv Health Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Bajaj Finserv Health Software Developer Intern