Question

Microsoft | OA Coding Questions and Solutions | Set - 91 | 2022

Answer 1

There are n butterflies and k colors.You have to color the butterflies, but you cant color two adjacent butterflies with the same color. There is also a special color(it could be one of the k colors or a different color). There is no coloring restriction while using the special color. You have to output the number of ways mod(1e9+7) of coloring the n butterflies….

 

Find the number of such possible arrangements after doing mod1e9+7 .

 

ip
5 4 3
op 469

 

5 2 3
op 2

Answer 2

/* We have to try all possibilities to fill the colors . Just make sure previous color is not used again (except a). Also every position has new problem with previous used color */

 

import java.util.;
public int getCount(int n, int k , int a){
/ Every position with previous used color becomes the sub problem.
So we need two dimension dp*/
int [][] dp = new int[k+1][n+1];
for(int [] d : dp){ /* Make sure dp filled with -1*/
Arrays.fill(d, -1);
}
/* Sending previous color as -1 (special case), n positions we need , k colors we can try, dp array , exception color a */
return solve(-1,n,k,dp,a);
}

 

public int solve(int pre, int n, int k, int [][] dp, int a){
           /* when n is 0 no positions to try  more and valid colors are filled */
	if(n==0)return 1;
	int ans = 0;
           /* Only first time previous color will be -1 otherwise we will have valid dp entry to check we already solved the problem */
	if(pre!=-1 && dp[pre][n]!=-1)return dp[pre][n];
            /* Try all possible color */
	for(int i=1;i<=k;i++){
                    /* if pre color is same as current skip but exceptional color is ok */
		if(i==pre && pre!=a)continue;
                    /*I am treating exceptional color separate but not needed */
		if(i==a)continue;
                    /* The next sub problem becomes 1 less position to try */
		ans += solve(i,n-1,k,dp,a);
		ans%=1000000007; /* Mod check*/
	}
	ans+=solve(a,n-1,k,dp,a);
	ans%=1000000007;
	if(pre!=-1){ /* updated all the time except very first case where there is no valid previous color issue */
		dp[pre][n]=ans;
	}
	return ans;
}

Answer 3

Simple DP. The modulo part is left as an exercise for the reader:

 

def color_butterflies(n, k, x):
  @lru_cache(None)
  def dp(n, c):
    if n == 1:
      return 1
    return sum(dp(n - 1, prev_c) for prev_c in range(k) if prev_c != c or c == x)
  return sum(dp(n, c) for c in range(k))

Answer 4

Similar to: https://leetcode.com/problems/paint-fence/

Answer 5

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll mod = 1e9 + 7;
ll fun(int i, int j, int k, int x, vector<vector> &dp)
{
if (i == 1)
return 1;
if (dp[i][j] != -1)
return dp[i][j];
ll sum = 0;
if (j == x)
{
for (int l = 1; l <= k; l++)
{

 

        sum = (sum + fun(i - 1, l, k, x, dp) + mod) % mod;
    }
    return dp[i][j] = sum;
}
else
{
    for (int l = 1; l <= k; l++)
    {
        if (j == l)
            continue;
        sum = (sum + fun(i - 1, l, k, x, dp) + mod) % mod;
    }
    return dp[i][j] = sum;
}

 

}
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k, x;
cin >> n >> k >> x;
vector<vector> dp(n + 2, vector(k + 2, -1));
cout << fun(n + 1, k + 1, k, x, dp) << "\n";
}
return 0;
}

Answer 6

https://www.hackerearth.com/challenges/competitive/pycon-2020/algorithm/butterfly-effect-8ca3e395/