Rings and Rods — Easy Problem & Solution

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…

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 even
2 <= rings.length <= 100
Colours are R, G or B; rod digits are 0 through 9.

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 i through the string in increments of two: rings[i] is the colour, rings[i+1] the rod digit.
OR the colour's bit (1 for R, 2 for G, 4 for B) into mask[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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue