Number of ways to color N | Java program for the above approach ; Recursive function to count the ways ; Base case ; Initialise answer to 0 ; Color each uncolored block according to the given condition ; If any block is uncolored ; Check if adjacent blocks are colored or not ; Color the block ; recursively iterate for next uncolored block ; Uncolored for the next recursive call ; Return the final count ; Function to count the ways to color block ; Mark which blocks are colored in each recursive step ; Function call to count the ways ; Driver Code ; Number of blocks ; Number of colored blocks ; Function call
import java . util . * ; class GFG { static int mod = 1000000007 ; static int countWays ( int colored [ ] , int count , int n ) { if ( count == n ) { return 1 ; } int answer = 0 ; for ( int i = 1 ; i < n + 1 ; i ++ ) { if ( colored [ i ] == 0 ) { if ( colored [ i - 1 ] == 1 colored [ i + 1 ] == 1 ) { colored [ i ] = 1 ; answer = ( answer + countWays ( colored , count + 1 , n ) ) % mod ; colored [ i ] = 0 ; } } } return answer ; } static int waysToColor ( int arr [ ] , int n , int k ) { int colored [ ] = new int [ n + 2 ] ; for ( int i = 0 ; i < k ; i ++ ) { colored [ arr [ i ] ] = 1 ; } return countWays ( colored , k , n ) ; } public static void main ( String [ ] args ) { int N = 6 ; int K = 3 ; int arr [ ] = { 1 , 2 , 6 } ; System . out . print ( waysToColor ( arr , N , K ) ) ; } }