Rings and Rods

Easy
662.

Rings and Rods

Rings and Rods is an easy coding problem on strings, hash table and bit manipulation, asked in Amazon, TCS and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} rings
 * @return {number}
 */
var countPoints = function(rings) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Rings and Rods

  1. Hint 1

    Walk the string two characters at a time — colour, then digit.

  2. Hint 2

    Each rod needs a three-bit set: one bit per colour.

  3. Hint 3

    A rod qualifies when its mask is 111 in 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

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