C++ program to find ways to color a skewed tree such that parent and child have different colors
Executable on C++11/14/17
Description and Approach:
This is practically a Combinatorics problem. The approach here is very simple, The root node of the skewed tree can be coloured in k ways where k is the total number of colours available, and for every other node (i.e remaining N-1 nodes), it has K-1 choices of colours as it cannot have the same colour as it's parent. So total number of ways = K X (K-1)^(N-1).
*Note: Skewed tree ->every node has at most one child.
Implementation:
using namespace std;
//Function to calculate power efficiently
long calc_power(long a, long b)
{
if( b == 0 )
return 1;
long chk = calc_power( a, b>>1 );
if(b & 1)
return a * chk * chk;
else
return chk * chk;
}
int main(int argc, char const *argv[])
{
long n, colors;
cout<<"Enter the number of nodes present in the skewed tree"<<endl;
cin>>n;
cout<<"enter the number of colours available (Must be > 1)"<<endl;
cin>>colors;
cout<<"The number of ways in which the skewed tree can be coloured is: "<<endl;
cout<<colors*calc_power(colors-1, n-1)<<endl;
return 0;
}
Time Complexity: O(log2(n)), Efficient method of calculating power is done in log2(n) time.
Sample Output:
gs_katti@gsk-47534B:~/Desktop/CppSecret$ g++ 22.skewed_color.cpp
s_katti@gsk-47534B:~/Desktop/CppSecret$ ./a.out
Enter the number of nodes present in the skewed tree
5
enter the number of colours available (Must be > 1)
6
The number of ways in which the skewed tree can be coloured is:
3750
Comments