1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Vector Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
C++ Code
3.4.
Python Code
3.5.
Complexity Analysis
4.
4.1.
What is the purpose of a sort() function in the code?
4.2.
What is the time complexity for the sort() STL function?
4.3.
What is the purpose of the "numSets" variable in the code?
4.4.
What data structure is used to store the number of balls in this code?
4.5.
What is the time complexity for accessing an element in a vector by its index?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Count of Arrangements of RGB balls with No Duplicates in a Set

Rishabh
0 upvote

## Introduction

Hey Ninjas!! Today we will look at a problem which involves intuition and observation skills. These kind of problem can often be asked during interviews, where you need to come up with a solution in a very short period of time.

Such problems are very interesting. So, why to wait? Let's jump to the problem.

## Problem Statement

Balls of three colors are given, red, green and blue. These RGB balls must be kept in sets where each set can contain 1, 2, or 3 balls. All balls in each set can be either of the same color or different colors. We have to calculate the minimum required sets to place all the balls.

### Example

Input

R = 2, G = 1, B = 2

Output

2

Explanation

Minimum of 2 sets will be required - {R, G, B}, {R, B}. Here both sets contain balls of different colors.

Also see, Euclid GCD Algorithm

## Vector Approach

This problem is an analysis-based problem, where the given conditions should be considered carefully. First, sort the number of balls in non-decreasing order and then calculate the number of sets with one ball of each color and three balls of the same color. Then, check for the remaining balls and calculate the minimum number of sets required to store them. Finally, return the total number of sets required.

### Algorithm

The problem mentioned above can be solved with the following steps:

• Generalize the condition as R <= G <= B by sorting them in order, as the number of sets won’t change with colors.

• Calculating sets containing balls of all three colors, which will be the minimum of {R, G, B} i.e., R.

• Now updating Green and Blue balls, by decreasing the number of Red balls from it, G’ = G - R and B’  = B - R.

• Now calculate the number of sets containing all three balls of only one color, which will be the sum of G / 3  and B / 3.

• Left green balls (G’ = G - R % 3) and blue balls (B’ = B - R % 3) can be covered with the below cases:

• G’ and B’ both are zero, so no more sets are required.

• G’ is 0, and B’ is one or two; only one set can accommodate B’ balls.

• G’ and B’ both are one; again, one set will be sufficient.

• In rest all cases, two sets will be required for the left G’ and B’ balls.

• Now getting the total of sets calculated in all steps gives the final answer

### Dry Run

• First, we create vector balls that contain red, green, and blue balls.
• balls is now {2, 1, 2}.

• Next, we sort the balls in non-decreasing order.
• balls is now {1, 2, 2}.

• We then calculate the number of sets with one ball of each color, which is equal to the minimum value in balls.
• numSets is now 1.

• We then subtract the number of balls used in the first set from the remaining colors, i.e., balls = {1-1, 2-1, 2-1}.
• balls is now {0, 1, 1}.

• We calculate the number of sets with three balls of the same color by dividing the number of remaining balls in each color by 3 i.e., balls = {0%3, 1%3, 1%3}.
• the balls are still {0, 1, 1}.

• Since there are no colors with at least 3 balls left, we don't add any sets in this step.

• We then calculate the remaining balls in each color after we have formed all possible sets of three, and one ball of each color.
• balls is still {0, 1, 1}.

• Finally, we check how many remaining balls we have and add the corresponding number of sets.

• Since we have one ball left in each of the red and blue colors, we add one set to the total.

• Therefore, the function returns 2, which is the minimum number of sets required to form all possible sets of one ball of each color from the given input.

### C++ Code

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calculateMinimumSets(int red, int green, int blue) {
// Store the number of balls in a vector.
vector<int> balls {red, green, blue};

// Sort the balls in non-decreasing order.
sort(balls.begin(), balls.end());

// Number of sets with one ball of each color.
int numSets = balls[0];
balls[1] -= balls[0];
balls[2] -= balls[0];
balls[0] = 0;

/*
Number of sets with three
balls of the same color.
*/
numSets += balls[1] / 3;
numSets += balls[2] / 3;

/*
remaining number of balls after
set of three has been formed
*/
balls[1] %= 3;
balls[2] %= 3;

/*
No more balls left.
Nothing happens with numSets.
*/
if (balls[1] == 0 && balls[2] == 0) {
numSets;
}
// Two balls left of the same color.
else if (balls[1] == 1 && balls[2] == 1) {
numSets++;
}
// Three balls left of different colors.
else if ((balls[1] == 2 && balls[2] == 0) || (balls[1] == 0 && balls[2] == 2)) {
numSets++;
}
// Two balls left of different colors.
else if (balls[1] == 1 || balls[2] == 1) {
numSets++;
}
// More than two balls left of different colors.
else {
numSets += 2;
}
// Return final numSets
return numSets;
}

int main() {
// Input
int red = 2;
int green = 1;
int blue = 2;

// Call the function and print the result
int minimumSets = calculateMinimumSets(red, green, blue);
cout << "Minimum required sets for RGB balls are " << minimumSets << endl;
return 0;
}``````

Output

### Python Code

``````def calculateMinimumSets(red, green, blue):
# Store the number of balls in a list.
balls = [red, green, blue]

# Sort the balls in non-decreasing order.
balls.sort()

# Number of sets with one ball of each color.
numSets = balls[0]
balls[1] -= balls[0]
balls[2] -= balls[0]

# Number of sets with three balls of the same color.
numSets += balls[1] // 3

numSets += balls[2] // 3

# Remaining number of balls after
# set of three has been formed
balls[1] %= 3
balls[2] %= 3

# No more balls left.
if balls[1] == 0 and balls[2] == 0:
pass

# Two balls left of the same color.
elif balls[1] == 1 and balls[2] == 1:
numSets += 1

# Three balls left of different colors.
elif (balls[1] == 2 and balls[2] == 0) or (balls[1] == 0 and balls[2] == 2):
numSets += 1

# Two balls left of different colors.
elif (balls[1] == 1 or balls[2] == 1):
numSets += 1

# Two balls left of different colors.
else:
numSets += 2
# Return final numSets
return numSets

# Input
red = 2
green = 1
blue = 2

# Call the function and print the result
minimumSets = calculateMinimumSets(red, green, blue)
print("Minimum required sets for RGB balls are", minimumSets)
``````

Output

### Complexity Analysis

Time complexity = O(1)

The time complexity is O(1) since the number of iterations required to compute the result does not depend on input size.
Pushing RGB balls into vector takes O(1) time. Further calculations for the most optimum answer, do not include any loop or function and require only O(1) time.

Space Complexity =  O(1)

The space complexity is also O(1) because only a fixed number of variables are used to store the information about the balls, and the size of the input does not affect the amount of memory used.

Check out this problem - Duplicate Subtree In Binary Tree

### What is the purpose of a sort() function in the code?

The sort() function in the code is used to sort the elements in non-decreasing order.

### What is the time complexity for the sort() STL function?

The time complexity of the sort() STL function is O(n log n) on average, where n represents the input length.

### What is the purpose of the "numSets" variable in the code?

The "numSets" variable is used to keep track of the number of sets required to group the balls.

### What data structure is used to store the number of balls in this code?

A vector is used to store the number of balls in this code.

### What is the time complexity for accessing an element in a vector by its index?

The time complexity for accessing an element in a vector by its index is O(1).

## Conclusion

In this blog, we learned to calculate the minimum required sets to place all the red, green and blue balls. We have implemented the problem in C++ and Python programming languages.

For more similar articles, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass