Painting Fence Algorithm | Returns count of ways to color k posts using k colors ; There are k ways to color first post ; There are 0 ways for single post to violate ( same color_ and k ways to not violate ( different color ) ; Fill for 2 posts onwards ; Current same is same as previous diff ; We always have k - 1 choices for next post ; Total choices till i . ; Driver code
function countWays ( n , k ) { let total = k ; let mod = 1000000007 ; let same = 0 , diff = k ; for ( let i = 2 ; i <= n ; i ++ ) { same = diff ; diff = total * ( k - 1 ) ; diff = diff % mod ; total = ( same + diff ) % mod ; } return total ; } let n = 3 , k = 2 ; document . write ( countWays ( n , k ) ) ;