Number of ways to color the balls (Ball Coloring)
Given N balls. All of them are initially uncolored. You have to color the balls with two colors RED and BLUE such that there can be at most 2 positions where a RED ball is touching BLUE ball or vice versa. You have to color all the balls. Find the number of ways in which balls can be colored.
Examples:
Input: n = 1
Output: 2
Explanation: Possible ways to color are {{R}, {B}}. So, the answer is 2.Input: n = 2
Output: 4
Explanation: Possible ways to color are {{RB}, {BR}, {RR}, {BB}}. So, the answer is 4.
Approach: To solve the problem, follow the below idea:
We can color all the balls in 3 ways.
- Zero red and blue balls are touching: We can color N balls in this way in 2 ways. For example: RRR , BBB is valid coloring for 3 balls.
- Red and Blue balls are touching at one place: We can color N balls in this way in 2*(N-1) ways. For example: RRB, RBB, BBR, BRR for 3 balls
- Red and Blue balls are touching at one place: In this case, we have to change the color of balls in 2 positions. For N balls we can choose 1st position in (N-1) ways and 2nd position in (N-2) ways. So we can color all the balls in (N-2)*(N-1) ways . Because at least First and Last Ball should have same color to satisfy the condition. For example: RBR, BRB
So total number of ways is ANS = 2 + 2 * (N-1) + (N-2) * (N-1) = 2 + N * (N-1)
Step-by-step algorithm:
- Input the value of N.
- Find the product as prod = N * (N – 1).
- Return prod + 2.
Below is the implementation of the approach:
C++
#include <iostream> using namespace std; unsigned long long int noOfWays(unsigned long long int n) { // code here unsigned long long int prod = n * (n - 1); return prod + 2; } int main() { // Input unsigned long long int n = 4; cout << noOfWays(n); return 0; } |
Java
public class Main { static long noOfWays( long n) { // code here long prod = n * (n - 1 ); return prod + 2 ; } public static void main(String[] args) { // Input long n = 4 ; System.out.println(noOfWays(n)); } } |
Python3
# Python Implementation def no_of_ways(n): prod = n * (n - 1 ) return prod + 2 n = 4 print (no_of_ways(n)) # This code is contributed by Tapesh(tapeshdu420) |
C#
using System; public class Program { static long NoOfWays( long n) { // code here long prod = n * (n - 1); return prod + 2; } public static void Main( string [] args) { // Input long n = 4; Console.WriteLine(NoOfWays(n)); } } |
Javascript
function noOfWays(n) { // code here let prod = n * (n - 1); return prod + 2; } // Input let n = 4; console.log(noOfWays(n)); |
14
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us