Rings and Rods — Solution in Python, Java & C++
Rings and Rods solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and TCS.
Rings and Rods is an easy coding problem on strings, hash table and bit manipulation, asked in Amazon, TCS and Infosys interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Bit Manipulation
- Asked at: Amazon, TCS, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are ten rods numbered 0 to 9. The string rings describes the rings on them in pairs: a colour character ('R' red, 'G' green, 'B' blue) followed by the rod digit it sits on.
Return how many rods carry all three colours.
Example 1
Input: rings = "B0B6G0R6R0R6"
Output: 1
Explanation: Rod 0 holds blue, green and red. Rod 6 holds only blue and red.
Example 2
Input: rings = "R0G0B1"
Output: 0
Explanation: Rod 0 is missing blue and rod 1 has only blue.
Example 3
Input: rings = "G4"
Output: 0
Constraints
rings.length is even2 <= rings.length <= 100Colours are R, G or B; rod digits are 0 through 9.
Hints for Rings and Rods
Hint 1
Walk the string two characters at a time — colour, then digit.
Hint 2
Each rod needs a three-bit set: one bit per colour.
Hint 3
A rod qualifies when its mask is
111in binary, which is 7.
How to solve Rings and Rods
Each rod's state is a set of at most three colours, which fits in three bits. Accumulate one bitmask per rod and count the rods whose mask is full.
Approach
- Step
ithrough the string in increments of two:rings[i]is the colour,rings[i+1]the rod digit. - OR the colour's bit (
1for R,2for G,4for B) intomask[rod]. - Count the rods whose mask equals
7.
Why it works
Bitwise OR is idempotent, so repeated rings of the same colour on the same rod cost nothing, and a mask of 7 is exactly 'all three bits present'.
Complexity
- Time —
O(n) - Space —
O(1) — ten masks
Pitfalls
- Stepping by one rather than two reads digits as colours and vice versa.
- Counting rings per rod instead of distinct colours: three red rings on one rod is not three colours.
Reference solution
Python
def countPoints(rings: str) -> int:
mask = [0] * 10
bits = {"R": 1, "G": 2, "B": 4}
for i in range(0, len(rings) - 1, 2):
colour = rings[i]
rod = ord(rings[i + 1]) - 48
if colour in bits and 0 <= rod <= 9:
mask[rod] |= bits[colour]
return sum(1 for m in mask if m == 7)Java
public static int countPoints(String rings) {
int[] mask = new int[10];
for (int i = 0; i + 1 < rings.length(); i += 2) {
char colour = rings.charAt(i);
int rod = rings.charAt(i + 1) - '0';
int bit = colour == 'R' ? 1 : (colour == 'G' ? 2 : 4);
if (rod >= 0 && rod <= 9) mask[rod] |= bit;
}
int total = 0;
for (int r = 0; r < 10; r++) {
if (mask[r] == 7) total++;
}
return total;
}C++
int countPoints(string rings) {
vector<int> mask(10, 0);
for (int i = 0; i + 1 < (int) rings.size(); i += 2) {
char colour = rings[i];
int rod = rings[i + 1] - '0';
int bit = colour == 'R' ? 1 : (colour == 'G' ? 2 : 4);
if (rod >= 0 && rod <= 9) mask[rod] |= bit;
}
int total = 0;
for (int r = 0; r < 10; r++) {
if (mask[r] == 7) total++;
}
return total;
}JavaScript
var countPoints = function(rings) {
var mask = [];
for (var t = 0; t < 10; t++) mask.push(0);
for (var i = 0; i + 1 < rings.length; i += 2) {
var colour = rings.charAt(i);
var rod = rings.charCodeAt(i + 1) - 48;
var bit = colour === "R" ? 1 : (colour === "G" ? 2 : 4);
mask[rod] |= bit;
}
var total = 0;
for (var r = 0; r < 10; r++) {
if (mask[r] === 7) total++;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets