# Painting Fence Algorithm in C++

In this article, we will discuss the Painting Fence Algorithm in C++ with its algorithm and multiple examples.

## Problem Statement:

If a fence has n posts and k colors, determine how many methods there are to paint it so that no more than two posts next to each other have the same color. Return the value modulo 10^9 + 7, as the answer may be huge.

Examples:

```Input: n = 2 k = 4.

Output: 16

Explanation: There are 2 posts and 4 colors.

Methods where the colors of the two posts match: 4

Methods in which the two posts differ in color:4 (first post selections) * 3 (second post choices) = 12

Input: n = 3 k = 2

Output: 6```

The six alternative ways to paint three posts with two colors are shown in the following image:

Examine the following image: i, i-1, and i -2 are represented by the colors c, c', and c" respectively.

The problem constraint is that c = c' = c" cannot occur simultaneously, so either c'!= c or c"!= c, or both. For the case of c'!= c and c"!= c, there are k – 1 possibilities.

### Algorithm:

```diff = number of ways when the color of the last
two posts are different
same = number of times in which the color of the previous two postings is the same

Total ways = diff + same

for n = 1
diff = k, same = 0
total = k

for n = 2
diff = k * (k-1) //k choices for
first post, k-1 for next
same = k/k choices for common
color of two posts
total = k +  k * (k-1)

for n = 3
diff = (all previous ways) * (k - 1)
(k+1) * (k-1) * (k-1)

same = previous diff ways
k * (k-1)

Hence, we deduce that,
total[i] = same[i] + diff[i]
same[i]  = diff[i-1]
diff[i]  = total[i-1] * (k-1)```

Example 1:

Let us take an example to illustrate the Painting Fence Algorithm in C++.

```#include <bits/stdc++.h>

using namespace std;

// Returns count of ways to color k posts

long countWays(int n, int k)

{

long dp[n + 1];

memset(dp, 0, sizeof(dp));

long long mod = 1000000007;

dp[1] = k;

dp[2] = k * k;

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

dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod;

}

return dp[n];

}

// Driver code

int main()

{

int n = 3, k = 2;

cout << countWays(n, k) << endl;

return 0;

}```

Output:

`6`

Example 2:

Let us take another example to illustrate the Painting Fence Algorithm in C++.

```#include <bits/stdc++.h>

using namespace std;

// yields the number of methods to color k posts.

// Using K colors

long countWays(int m, int l)

{

// The first post can be colored in k ways.

long total = l;

int mod = 1000000007;

// One post can be made in 0 ways to

// both (same color) and k methods to

// not violate (different color)

int same = 0, diff = l;

// Fill for the next two posts.

for (int o = 2; o <= m; o++) {

same = diff;

// The current differs from the previous one.

// For the next post, we always have k-1 alternatives.

diff = (total * (l - 1)) % 1000000007;

// total options up until I.

total = (same + diff) % mod;

}

}

// Code for the driver

int main()

{

int m = 3, l = 2;

cout << countWays(m, l) << endl;

return 0;

}```

Output:

`6`

Example 3:

Let us take an example to illustrate the Painting Fence Algorithm in C++.

```#include <iostream>

using namespace std;

int minHeight(int *arr, int cnt)

{

int minValue = arr[0];

for (int i = 1; i < cnt; i++)

if (minValue > arr[i])

minValue = arr[i];

return minValue;

}

int recursive(int *arr, int cnt)

{

if (cnt == 1)

return 1;

int minValue = minHeight(arr, cnt);

int rest = 0;

int count = 0;

int start = 0;

for (int i = 0; i < cnt; i++)

{

arr[i] -= minValue;

if (arr[i] == 0)

{

if (count == 0)

{

start = i + 1;

continue;

}

else

{

rest += recursive(arr + start, count);

start = i + 1;

count = 0;

}

}

else

count++;

}

if (count != 0)

rest += recursive(arr + start, count);

if (minValue + rest < cnt)

return minValue + rest;

else

return cnt;

}

int main(void)

{

int n;

cin >> n;

int *a = new int[n];

for (int i = 0; i < n; i++)

cin >> a[i];

cout << recursive(a, n) << endl;

delete[] a;

return 0;

}```

Output:

```1

2

1```