• This is the recursive solution, it can be memoized to get a solution of time complexity 0(n)

int fun(int i,int prev,int first_node,int n) {

// three different colors 1,2,3 // here i is state, prev is the color of previous node,first_node is color of first node, n is total number of nodes if(i==n) { int ans=0;

for(int k=1;k<=3;k++)
   if(k!=prev and k!=first_node)//for the last node we can't paint color of first node and color of previous node 
     ans++;

   return ans;

} if(i==1) { int a=0,b=0,c=0; //for the first node we can paint any color a=fun(i+1,1,1,n); b=fun(i+1,2,2,n); c=fun(i+1,3,3,n);

return a+b+c;

}

int ans=0;
   //for any other node we can paint a color that is different from previous one 
 for(int k=1;k<=3;k++)
 { 
   if(k!=prev)
     ans+=fun(i+1,k,first_node,n);
 }

 return ans;

}

int findans(int n) { int ans=fun(1,-1,-1,n);

return ans; }