|
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)
{
unsigned long long int prod = n * (n - 1);
return prod + 2;
}
int main()
{
unsigned long long int n = 4;
cout << noOfWays(n);
return 0;
}
|
Java
public class Main {
static long noOfWays(long n) {
long prod = n * (n - 1);
return prod + 2;
}
public static void main(String[] args) {
long n = 4;
System.out.println(noOfWays(n));
}
}
|
Python3
def no_of_ways(n):
prod = n * (n - 1)
return prod + 2
n = 4
print(no_of_ways(n))
|
C#
using System;
public class Program
{
static long NoOfWays(long n)
{
long prod = n * (n - 1);
return prod + 2;
}
public static void Main(string[] args)
{
long n = 4;
Console.WriteLine(NoOfWays(n));
}
}
|
Javascript
function noOfWays(n) {
let prod = n * (n - 1);
return prod + 2;
}
let n = 4;
console.log(noOfWays(n));
|
Time Complexity: O(1)
Auxiliary Space: O(1)
|
